题意:
1． 表达式只可能包含一个变量‘a’。
2． 表达式中出现的数都是正整数，而且都小于10000。
3． 表达式中可以包括四种运算‘+’（加），‘-’（减），‘*’（乘），‘^’（乘幂），以及小括号‘(’，‘)’。小括号的优先级最高，其次是‘^’，然 后是‘*’，最后是‘+’和‘-’。‘+’和‘-’的优先级是相同的。相同优先级的运算从左到右进行。（注意：运算符‘+’，‘-’，‘*’，‘^’以及 小括号‘(’，‘)’都是英文字符）
4． 幂指数只可能是1到10之间的正整数（包括1和10）。
5． 表达式内部，头部或者尾部都可能有一些多余的空格。
下面是一些合理的表达式的例子：
((a^1) ^ 2)^3，a*a+a-a，((a+a))，9999+(a-a)*a，1 + (a -1)^3，1^10^9……
input:
( a + 1) ^2
3
(a-1)^2+4*a
a + 1+ a
a^2 + 2 * a * 1 + 1^2 + 10 -10 +a -a
output:
AC
思路：可能会想到将表达式展开问题，但是编码难度很大。。题目中有关键信息，就是幂指数最大为10，这样就是一个最高次为10的多项式方程。我们只需要代入十一个点进去，看是否两个方程的答案相同，即可判断出两个表达式是否等价；
细节:使用单调栈来计算表达式的值；处理下优先级即可；特别注意在不要mod = 1e9+7时还是最好用long long。。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include <map> #include <ctime> #include<bits/stdc++.h> using namespace std; #define rep0(i,l,r) for(int i = (l);i < (r);i++) #define rep1(i,l,r) for(int i = (l);i <= (r);i++) #define rep_0(i,r,l) for(int i = (r);i > (l);i--) #define rep_1(i,r,l) for(int i = (r);i >= (l);i--) #define inf 0x7fffffff #define MS0(a) memset(a,0,sizeof(a)) typedef long long ll; template<typename T> void read1(T &m) { T x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} m = x*f; } template<typename T> void read2(T &a,T &b){read1(a);read1(b);} template<typename T> void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);} char s[55],t[55]; const int mod = 1e9+7; int add(int a, int b) { return (a+b)%mod; } int sub(ll a, ll b) { return ((a-b)%mod + mod)%mod; } int mult(ll a, ll b) { return ((a%mod) * (b%mod))%mod; } ll pow(ll a,ll b) { ll ans = 1; while(b){ if(b&1) (ans *= a) %= mod; (a *= a) %= mod; b >>= 1; } return ans; } char stk[55]; ll v[55]; map<char,int> mp; int solve(char *s,int val) { int len = strlen(s),p = 1,top = 0; stk[1] = '(';s[len++] = ')';s[len] = ' '; for(int i = 0;i < len;i++)if(s[i] != ' '){ if(s[i] == 'a' || (s[i] >= '0' && s[i] <= '9')){ if(s[i] == 'a') v[++top] = val; else{ int t = 0; while(s[i] >= '0' && s[i] <= '9') t = t*10+s[i++]-'0'; i--;v[++top] = t; } }else{ if(s[i] == '('){ stk[++p] = '('; continue; } while(p && mp[s[i]] >= mp[stk[p]]){ if(stk[p] == '^') v[top-1] = pow(v[top-1],v[top]); else if(stk[p] == '*') v[top-1] = mult(v[top-1],v[top]); else if(stk[p] == '+') v[top-1] = add(v[top-1],v[top]); else if(stk[p] == '-') v[top-1] = sub(v[top-1],v[top]); if(stk[p--] == '(') break; top--; } if(s[i] != ')') stk[++p] = s[i]; } } return v[1]; } int d[15],val[15]; int main() { mp['^'] = 1;mp['*'] = 2,mp['+'] = 3,mp['-'] = 3,mp['('] = 4,mp[')'] = 5; gets(s); int n; read1(n); srand(time(0)); rep1(j,1,11){ //随机产生11个数； d[j] = rand()%107; val[j] = solve(s,d[j]); } rep0(i,0,n){ gets(t); int flag = 1; rep1(j,1,11){ if(val[j] != solve(t,d[j])){ flag = 0; break; } } if(flag) putchar('A'+i); } return 0; }