记录编号	44860	评测结果	AAAAAAAAAA
题目名称	[NOIP 2005]等价表达式	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2012-10-20 17:52:19	内存使用	3.28 MiB

#include<iostream>
#include<fstream>
#include<stack>
#include<climits>
#include<cstdio>
#include<cstring>
using namespace std;
ifstream fin("equal.in");
ofstream fout("equal.out");
//"表达式求值"内容都是从PPT上粘过来的......
stack<char> s2;//运算符栈
stack<long long> s1;//数字栈
char s[52];//输入串
const long long N=INT_MAX/2;
long long invo(long long x,long long y){//x^y mod max
	long long ans=1,i;
	x%=N;
	for(i=1;i<=y;i++){
		ans%=N;
		ans*=x;
		ans%=N;
	}
	return ans;
}
int fg(char x){//判定运算符等级
	if(x=='+'||x=='-') return 1;
	if(x=='*'||x=='/') return 2;
	if(x=='^') return 3;
	return 0;
}
void op(char x){
	int a,b;
	while (!s2.empty()&&fg(s2.top())>=fg(x)){//级别高的运算符先处理
	   a=s1.top();s1.pop();b=s1.top();s1.pop();
	   switch (s2.top()){
		  case'+':s1.push((b+a)%N);break;
		  case'-':s1.push((b-a%N));break;
		  case'*':s1.push(((b%N)*(a%N))%N);break;
		  case'^':s1.push(invo(b,a));break;
		  default:s1.push(-1);
	   }	   
	   s2.pop();
	}
	s2.push(x);//运算符入栈
}
void right(){
	int a,b;
	while (s2.top()!='('){//括号内运算符处理
	    a=s1.top();s1.pop();b=s1.top();s1.pop();//栈中弹出数据a,b
	    switch (s2.top()){//根据运算符计算
			case'+':s1.push((b+a)%N);break;
			case'-':s1.push((b-a%N));break;
			case'*':s1.push(((b%N)*(a%N))%N);break;
			case'^':s1.push(invo(b,a));break;
			default:s1.push(-1);
	    }
		s2.pop();//运算符使用完毕，出栈
	}
	s2.pop();//左括号出栈
}
long long compute(int a){
	while(!s1.empty()) s1.pop();
	while(!s2.empty()) s2.pop();//清空
	for(int i=0;i<strlen(s);i++){
		if(s[i]>='0'&&s[i]<='9'){
			if(i>0&&'0'<=s[i-1]&&s[i-1]<='9'){
				long long temp=s1.top();
				s1.pop();
				s1.push(temp*10+s[i]-'0');
			}
			else s1.push(s[i]-'0');
		}
		else if(s[i]=='a') s1.push(a);
		else if(s[i]=='(') s2.push(s[i]);
		else if(s[i]==')') right();
		else if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='^'||s[i]=='#') op(s[i]);
	}
	return s1.top();
}
int main(){
	int a,n,i;
	long long ini[11]={0},now[11]={0};
	fin.getline(s,51);
	s[strlen(s)]='#';//加一个#保证全部运算符都运算
	for(a=-5;a<=5;a++) ini[a+5]=compute(a)%N;
	fin>>n;
	bool flag;
	char ch;
	fin.get(ch);
	for(i=0;i<n;i++){
		memset(s,0,51);
		fin.getline(s,51);
		s[strlen(s)]='#';
		flag=true;
		for(a=0;a<=5;a++){
			now[a+5]=compute(a)%N;
			if(now[a+5]!=ini[a+5]){
				flag=false;
				break;
			}
		}
		if(flag) fout<<(char)(i+'A');
	}
	cout<<endl;
	return 0;
}