记录编号	27890	评测结果	AAAAAAAAAA
题目名称	[NOIP 2005]等价表达式	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.045 s
提交时间	2011-10-09 22:07:00	内存使用	0.27 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

long long check=23,
		  result_t,
		  final;
long long num[50],//數字棧
		  op[50]; //運算符號棧

long long power(long long a,long long b)
{
	long long k=1;
	for(int i=0;i<b;i++)
		k*=a;
	return k;
}

//操作棧頂的兩個元素
void cul(int p,int op)
{
	if(op==0) num[p-1]=num[p-1]+num[p];
	if(op==1) num[p-1]=num[p-1]-num[p];
	if(op==2) num[p-1]=num[p-1]*num[p];
	if(op==5) num[p-1]=power( num[p-1],num[p] );
}

long long result(string str)
{
	int op_nxt,//下一個即將入棧操作符
		len=str.length(),
		p=-1,q=-1;  //數字棧、符號棧的指針
	long long num_nxt=0;//下一個即將入棧的數字
	for(int i=0;i<len;i++)
	{
		if(str[i]=='a')
		{
			num[++p]=check;
		}
		else if(str[i]>='0' && str[i]<='9')
		{
			num_nxt=num_nxt*10+(str[i]-'0');
		}
		else if(str[i]!=' ')
		{
			if( num_nxt!=0) 
			{
				num[++p]=num_nxt;
				num_nxt=0;
			}
			if(str[i]=='+') op_nxt=0;
			if(str[i]=='-') op_nxt=1;
			if(str[i]=='*') op_nxt=2;
			if(str[i]=='^') op_nxt= 5;
			if(str[i]=='(') op_nxt=6;
			if(str[i]==')') op_nxt=7;
			//如果有括號，則括號的優先級最高
			if(op_nxt==6)
			{
				op[++q]=op_nxt;
			}
			else if(op_nxt==7)
			{
				while(q>=0 && op[q--]!=6)
				{ //從上一個與該右括號匹配的左括號開始處理括號內的表達式
					cul(p--,op[q+1]);
				}
			}
			
			else 
			{	//從棧頂開始，把優先級高的運算符出棧
				while( q >= 0 && op[q] <= 5 && op[q]/2>=op_nxt/2)
				{
					cul(p--,op[q--]);
				}
				op[++q]=op_nxt;
			}
		}
	}
	//在最後清空堆棧
	if(num_nxt!=0)
	{
		num[++p]=num_nxt;
		num_nxt=0;
	}
	while(q>=0)
	{
		cul(p--,op[q--]);
	}
	return num[0];
}

int main() 
{
	freopen("equal.in","r",stdin);
	freopen("equal.out","w",stdout);
	string str1,str2;
	int n;
	final=0;
	getline(cin,str1);
	cin>>n;
	getline(cin,str2);//過濾換行符
	while(n--)
	{
		bool flag=true;
		getline(cin,str2);
		for (int i=10;i<=20;i++)
		{
			check=i;
			if (result(str1)!=result(str2))
			{
				flag=false;
				break;
			}
		}
		if (flag) cout<<(char)('A'+final);
		final++;
	}
	cout<<endl;
	return 0;
}