首页 > ACM题库 > HDU-杭电 > HDU 3350-#define is unsafe-栈-[解题报告]HOJ
2014
03-16

HDU 3350-#define is unsafe-栈-[解题报告]HOJ

#define is unsafe

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

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))

样例输出:

1 0
2 1
3 1
4 2
5 2
28 14

考试前就停在这题上,和表达式求值很像,当时想用波兰符号法写,考完试后,就用栈来写了,这里运算符只有‘+’,所以不用处理那些优先级,就变的很简单了,读入数字时,当符号栈顶是+,那么就和前一个数运算,当读入到‘,’或‘)’时,如果栈顶还有‘+’那么就进行运算,直到是‘(’,最后就只剩一个数了,和表达式求值基本上是一样的,不过这个简单点。

Run ID Submit Time Judge Status Pro.ID Exe.Time Exe.Memory Code Len. Language Author
5232754 2012-01-06 16:49:34 Accepted 3350 0MS 212K 1733 B C++ xym2010
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<stack>
using namespace std;
struct state
{
	int tot,num;
}tem,in,out;
stack <struct state> st;
stack < char > cst;
int n,m;
char s[10005];
int main()
{
	int t;
	scanf("%d",&t);getchar();
	while(t--)
	{
		gets(s);
		int len=strlen(s);
		for(int i=0;i<len;i++)
		{
			if(s[i]<='9'&&s[i]>='0')
			{
				int tep=0;
				while(s[i]<='9'&&s[i]>='0')
				{
					tep=tep*10+s[i]-'0';
					i++;
				}
				if(!cst.empty()&&cst.top()=='+')
				{
					tem=st.top();st.pop();
					tem.num+=tep;tem.tot++;
					st.push(tem);cst.pop();
				}
				else
				{
					tem.num=tep;tem.tot=0;
					st.push(tem);
				}
				i--;
			}
			else if(s[i]=='+'||s[i]=='(')
				cst.push(s[i]);
			else if(s[i]==')'||s[i]==',')
			{
				while(!cst.empty()&&cst.top()=='+')
				{
					in=st.top();st.pop();
					out=st.top();st.pop();
					tem.num=in.num+out.num;
					tem.tot=in.tot+out.tot+1;
					st.push(tem);cst.pop();
				}
				if(s[i]==')'&&st.size()>=2)
				{
					in=st.top();st.pop();
					out=st.top();st.pop();
					if(out.num>in.num)
					{
						out.tot=out.tot*2+in.tot;
						st.push(out);
					}
					else
					{
						in.tot=in.tot*2+out.tot;
						st.push(in);
					}
					cst.pop();
				}
			}
		}
		while(!cst.empty())
		{
			while(!cst.empty()&&cst.top()=='+')
			{
				in=st.top();st.pop();
				out=st.top();st.pop();
				tem.num=in.num+out.num;
				tem.tot=in.tot+out.tot+1;
				st.push(tem);
				cst.pop();
			}
		}
		printf("%d %d\n",st.top().num,st.top().tot);
		st.pop();
	}
	return 0;
}

参考:http://blog.csdn.net/xymscau/article/details/7181888


,
  1. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  2. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

  3. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.