【HDU3350】#define is unsafe(前缀表达式求值)

Categories: 数据结构和算法
Tags: , ,
Comments: No Comments
Published on: 2011 年 05 月 12 日

Have you used #define in C/C++ code like the code below?
#include
#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
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.

题意:计算define宏定义出来的MAX在表达式中计算加法的总次数。
题解:用前缀表达式求值或者后缀表达式求值计算。括号内的中缀转换成相应的前缀或者后缀。
对前缀、中缀、后缀表达式不太了解的请看:
http://blog.pureisle.net/archives/96.html

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<string>
#include<list>
#include<sstream>
#include<vector>
using namespace std;
#define CLR(arr,val) memset(arr,val,sizeof(arr))

int mystoi(string s)
{
	int i;
	sscanf(s.c_str(),"%d",&i);
	return i;
}
bool isdigit(string s)
{
	return (s[0]<='9'&&s[0]>='0' || s[0]=='-');
}
int getNext(stringstream& ss)
{
	char c=ss.get();
	int num;
	switch(c)
	{
	case 'M':ss.get();ss.get();return -1;
	case '+':return -2;
	case '(':return -3;
	case ')':return -4;
	case ',':return -5;
	case EOF:return -6;
	default:ss.unget();ss>>num;return num;
	}
}
list<int>::iterator lastinsert(list<int>::iterator it)
{
	if(*--it>=0) return it;
	int cnt=1;
	while(cnt>0)
	{
		--it;
		if(*it==-4) cnt++;
		else if(*it==-3) cnt--;
	}
	return --it;
}
list<int>::iterator itstart;
pair<int,int> ind()
{
	pair<int,int> p1,p2;
	++itstart;
	switch(*itstart)
	{
	case -3:
	case -4:
	case -5:return ind();
	case -1:p1=ind(),p2=ind();if(p1.first>p2.first) return make_pair(p1.first,p1.second*2+p2.second);else return make_pair(p2.first,p1.second+p2.second*2);
	case -2:p1=ind(),p2=ind();return make_pair(p1.first+p2.first,p1.second+p2.second+1);
	default:return make_pair(*itstart,0);
	}
}

int main()
{
	//freopen("in.txt","r",stdin);
	int t,n;
	string line;
	scanf("%d",&t);
	getchar();
	while(t--)
	{
		list<int> exp;
		exp.push_back(-5);
		exp.push_back(-5);
		getline(cin,line);
		stringstream ss(line);
		while((n=getNext(ss))!=-6)
		{
			switch(n)
			{
			case -5:
			case -4:
			case -1:
			default:
			case -3:exp.push_back(n);break;
			case -2:exp.insert(lastinsert(exp.end()),-2);break;
			}
		}
		itstart=exp.begin();
		pair<int,int> p=ind();
		printf("%d %d\n",p.first,p.second);
	}
}

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期六, 2017 年 10 月 21 日