【NOIP2005提高组T4】等价表达式+模拟+栈

测试地址：等价表达式

做法：这个题目我首先想到的方法是，展开表达式，存储未知数a的各个次幂的系数，展开每个表达式后再进行对比。但这样子很难处理，于是就想到把一些较大的质数代入表达式求解，然后比较，多代入几个质数，如果结果都相同，那么两个表达式就基本上等价了。至于表达式的计算，用栈的方法模拟即可。

以下是本人代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <stack>
#define mod 100000007
using namespace std;
int n,p[6]={0,1187,1291,1523,1759,1933}; //要代入的大质数
int len,pos[210],pi;
long long ans[6],val[6];
char s[210],a[210];

void read() //读入表达式，并手动把其中的空格去掉，以便后面的操作
{
  gets(s);
  int slen=strlen(s);
  len=0;
  for(int i=0;i<slen;i++)
    if (s[i]!=' ') a[++len]=s[i];
}

long long power(long long x,int y) //快速幂求x^y（不用应该也可以...一开始没看到幂指数≤10这个条件）
{
  long long s=1,tmp=x;
  while(y!=0)
  {
    if (y&1) s=(s*tmp)%mod;
    tmp=(tmp*tmp)%mod;y>>=1;
  }
  return s%mod;
}

long long number(int l,int r) //计算字符串中[l,r]一段代表的数字
{
  long long s=0;
  for(int i=l;i<=r;i++)
    s=(s*10+a[i]-'0')%mod;
  return s%mod;
}

long long work(int l,int r) //求表达式的值
{
  int i;
  for(i=r;i>=l;i--)
  {
    if (a[i]==')') i=pos[i];
	else if (a[i]=='+'||a[i]=='-') break;
  }
  if (i>=l)
  {
    long long x,y;
	x=(work(l,i-1)+mod)%mod;
	y=(work(i+1,r)+mod)%mod;
	if (a[i]=='+') return (x+y)%mod;
	else return (x-y+mod)%mod;
  }
  for(i=r;i>=l;i--)
  {
    if (a[i]==')') i=pos[i];
	else if (a[i]=='*') break;
  }
  if (i>=l)
  {
    long long x,y;
	x=(work(l,i-1)+mod)%mod;
	y=(work(i+1,r)+mod)%mod;
	return (x*y)%mod;
  }
  for(i=r;i>=l;i--)
  {
    if (a[i]==')') i=pos[i];
	else if (a[i]=='^') break;
  }
  if (i>=l)
  {
    long long x,y;
	x=(work(l,i-1)+mod)%mod;
	y=(work(i+1,r)+mod)%mod;
	return power(x,y)%mod;
  }
  if (a[r]==')') return work(l+1,r-1);
  if (a[r]=='a') return p[pi];
  return number(l,r);
}

void calc(bool mode)
{
  stack<int> b;
  for(int i=len;i>=1;i--)
  {
    if (a[i]==')') b.push(i);
	if (a[i]=='(')
	{
	  pos[b.top()]=i;
	  b.pop();
	}
  }
  for(pi=1;pi<=5;pi++)
  {
    long long value=(work(1,len)+mod)%mod;
	if (!mode) ans[pi]=value;
	else val[pi]=value;
  }
}

int main()
{
  read();
  calc(0);
  
  scanf("%d",&n);getchar();
  for(int i=0;i<n;i++)
  {
    read();
	calc(1);
	int j;
	for(j=1;j<=5;j++)
	  if (val[j]!=ans[j]) break;
	if (j>5) printf("%c",'A'+i);
  }
  
  return 0;
}