O(1000*26*n)

【算法分析】 表达式的化简相对来说比较麻烦，这个时候我们可以代入特殊值，然后计算的过程可能数值比较大，我们进行取模即可。

#include<bits/stdc++.h>
using namespace std;
stack<int> num;
stack<char> ops;
map<char,int> pr;
const int P=13331;
void evl() //单次计算
{
    int b=num.top();num.pop();
    int a=num.top();num.pop();
    char c=ops.top();ops.pop();
    int t;
    if(c=='+') t=a+b;
    else if(c=='-') t=a-b;
    else if(c=='*') t=a*b%P;
    else
    {
        t=1;
        for(int i=1;i<=b;i++)
        {
            t=(t*a)%P;
        }
    }
    num.push((t%P+P)%P);
}
int cal(string s,int a) //中缀表达式模板
{
    while(num.size()) num.pop(); //清空数据
    int n=s.size();
    for(int i=0;i<n;i++)
    {
        if(s[i]==' ') continue;
        else if(s[i]=='a') num.push(a);
        else if(isdigit(s[i]))
        {
            int t=0;
            int j=i;
            while(j<n&&isdigit(s[j]))
            {
                t=t*10+s[j]-'0';
                j++;
            }
            j--;
            i=j;
            num.push(t);
        }
        else if(s[i]=='(') ops.push(s[i]);
        else if(s[i]==')')
        {
            while(ops.size()&&ops.top()!='(')
            {
                evl();
            }
            ops.pop();
        }
        else
        {
            while(ops.size()&&pr[ops.top()]>=pr[s[i]])
            {
                evl();
            }
            ops.push(s[i]);
        }
    }
    while(ops.size()) evl();
    return num.top();
}
bool check(string a,string b) //判断给定范围内的数算出来的表达式是否相等
{
    for(int i=0;i<=1000;i++)
    {
        if(cal(a,i)!=cal(b,i)) return false;
    }
    return true;
}
int main()
{
    pr['+']=pr['-']=1;
    pr['*']=2,pr['^']=3;
    string s,t;
    getline(cin,s);
    int n;
    cin>>n;
    getline(cin,t);
    string res;
    for(int i=0;i<n;i++) //枚举当前表达式和给定的表达式
    {
        getline(cin,t);
        if(check(s,t))
        {
            res=res+char('A'+i);
        }
    }
    cout<<res;
}