HDU 3350 #define is unsafe 解题报告

#define is unsafe

Description

Have you used #define in C/C++ code like the code below?

#include <stdio.h>
#define MAX(a , b) ((a) > (b) ? (a) : (b))
int main()
{
printf(“%d\n” , MAX(2 + 3 , 4));
return 0;
}

Run the code and get an output: 5, right?
You may think it is equal to this code:

#include <stdio.h>
int max(a , b) {  return ((a) > (b) ? (a) : (b));  }
int main()
{
printf(“%d\n” , max(2 + 3 , 4));
return 0;
}

But they aren’t.Though they do produce the same anwser , they work in two different ways.
The first code, just replace the MAX(2 + 3 , 4) with ((2 + 3) > (4) ? (2 + 3) : 4), which calculates (2 + 3) twice.
While the second calculates (2 + 3) first, and send the value (5 , 4) to function max(a , b) , which calculates (2 + 3) only once.

What about MAX( MAX(1+2,2) , 3 ) ?
Remember “replace”.
First replace: MAX( (1 + 2) > 2 ? (1 + 2) : 2 , 3)
Second replace: ( ( ( 1 + 2 ) > 2 ? ( 1 + 2 ) : 2 ) > 3 ? ( ( 1 + 2 ) > 2 ? ( 1 + 2 ) : 2 ) : 3).
The code may calculate the same expression many times like ( 1 + 2 ) above.
So #define isn’t good.In this problem,I’ll give you some strings, tell me the result and how many additions(加法) are computed.

Input

The first line is an integer T(T<=40) indicating case number.
The next T lines each has a string(no longer than 1000), with MAX(a,b), digits, ‘+’ only(Yes, there’re no other characters).
In MAX(a,b), a and b may be a string with MAX(c,d), digits, ‘+’.See the sample and things will be clearer.

Output

For each case, output two integers in a line separated by a single space.Integers in output won’t exceed 1000000.

Sample Input

6

MAX(1,0)

1+MAX(1,0)

MAX(2+1,3)

MAX(4,2+2)

MAX(1+1,2)+MAX(2,3)

MAX(MAX(1+2,3),MAX(4+5+6,MAX(7+8,9)))+MAX(10,MAX(MAX(11,12),13))

Sample Output

1 0

2 1

3 1

4 2

5 2

28 14

Source

HDU2010省赛集训队选拔赛（校内赛）

思路：类似表达式求值，用栈模拟计算过程。开一个数字栈一个符号栈，从头开始扫一遍，忽略MAX，扫到(或+压栈，扫到数字就计算出整个数字后压栈，扫到,将左边加法计算完毕压栈，扫到)先将左边加法计算完毕再比较大小，这里注意计算次数的处理，大的一边计算次数要*2再加到总次数中。扫完以后栈里面可能还有没处理的数，但肯定全是加法，相加后即得到答案。

AC代码：

#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
char buf[1010];
struct node
{
	int val, add;
};
stack <node> num;
stack <char> sig;
void input()
{
	scanf("%s", buf);
}
void solve()
{
	while (!num.empty())
		num.pop();
	while (!sig.empty())
		sig.pop();
	int len = strlen(buf);
	node tmp;
	for (int i = 0; i < len; i++)
	{
		if (buf[i] == '(' || buf[i] == '+')
			sig.push(buf[i]);
		else if (buf[i] >= '0' && buf[i] <= '9')
		{
			tmp.val = tmp.add = 0;
			while (buf[i] >= '0' && buf[i] <= '9')
				tmp.val = tmp.val * 10 + buf[i++] - '0';
			i--;
			num.push(tmp);
		}
		else if (buf[i] == ',')
		{
			while (!sig.empty() && sig.top() == '+')
			{
				sig.pop();
				tmp = num.top();
				num.pop();
				tmp.val += num.top().val;
				tmp.add += num.top().add + 1;
				num.pop();
				num.push(tmp);
			}
		}
		else if (buf[i] == ')')
		{
			while (!sig.empty() && sig.top() == '+')
			{
				sig.pop();
				tmp = num.top();
				num.pop();
				tmp.val += num.top().val;
				tmp.add += num.top().add + 1;
				num.pop();
				num.push(tmp);
			}
			sig.pop();
			tmp = num.top();
			num.pop();
			if (tmp.val < num.top().val)
			{
				tmp.val = num.top().val;
				tmp.add += num.top().add * 2;
			}
			else
				tmp.add = tmp.add * 2 + num.top().add;
			num.pop();
			num.push(tmp);
		}
	}
	while (!sig.empty() && sig.top() == '+')
	{
		sig.pop();
		tmp = num.top();
		num.pop();
		tmp.val += num.top().val;
		tmp.add += num.top().add + 1;
		num.pop();
		num.push(tmp);
	}
	printf("%d %d\n", num.top().val, num.top().add);
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		input();
		solve();
	}
	return 0;
}