一道很神奇的题目。对于算术表达式一类的问题，可以采用编译原理里的后缀表达式的方式来做，具体做法是分别维护两个栈，一个栈里保存表达式里的数字，另一个栈里保存表达式里的运算符，给每种运算符一个优先级，我们要维护这个栈的单调性，每次读入运算符中的数字或运算符，读入的是运算符时，若这个运算符比栈顶的运算符优先级低，就弹出栈顶元素，把栈顶的运算符和数字栈里栈顶的两个数字拿出来做一次运算，运算结果再入数字栈，直到运算符栈的栈顶元素优先级比这个运算符低为止。

然后题目有坑点，一是读入的表达式字符串可能有空格，所以不能直接scanf一次搞定读入数据操作。二是判断表达式是否等价时，带入的值如果不好可能会WA，所以为了避免这种情况的发生，我们代入的数字应该是个小数，用三态函数判断表达式结果是否相等，多代入几个小数计算，基本上不可能出现意外WA的发生。

#include <iostream>#include <stdio.h>#include <string.h>#include <stdlib.h>#include <algorithm>#include <map>#include <cmath>#define MAXN 1000#define EPS (1e-5)using namespace std;long long stackOfNum[MAXN];int topNum=0; //保存数字的栈和栈顶下标char stackOfSign[MAXN];int topSign=0; //保存运算符号的栈和栈顶下标bool needPop[50][50]; //needPop[i][j]=true表示当前运算符为i,栈顶运算符为j时需要出栈bool isTrue[30];int dcmp(long long a,long long b) //a>b return 1; a=b return 0; a<b return -1{    if(fabs(a-b)<=EPS)        return 0;    if(a>b)        return 1;    return -1;}long long cal(long long a,long long b,char cmd){    switch(cmd)    {        case '^':        {            long long ans=1;            for(int i=1;i<=(int)b;i++)                ans*=a;            return ans;        }        case '+': return a+b;        case '-': return a-b;        case '*': return a*b;        case '/': return a/b;    }    return 0;}long long getAns(char s[],int len,long long a) //将表达式的值求出来，len=表达式长度,a=字母a对应的值{    int p=1; //指针指向当前的表达式下标    topNum=0;    topSign=0;    while(p<=len)    {		while(s[p]==' ') p++;		if(p>len) break;        if(s[p]>='0'&&s[p]<='9') //是数字        {            int nowNum=0;            while(p<=len)            {                if(!(s[p]>='0'&&s[p]<='9')) //现在的s[p]不是数字了                    break;                nowNum*=10;                nowNum+=s[p]-'0';                p++;            }            stackOfNum[++topNum]=nowNum; //这个数字进栈            continue;        }        else if(s[p]=='a')            stackOfNum[++topNum]=a; //如果是a，将a对应的数字压入栈        else //s[p]是个运算符,将栈中所有比它优先级        {            while(topSign>0&&topNum>0)            {                if(needPop[s[p]][stackOfSign[topSign]])                {                    if(stackOfSign[topSign]=='(') //右括号遇到左括号                    {                        topSign--;                        break;                    }                    stackOfNum[topNum-1]=cal(stackOfNum[topNum-1],stackOfNum[topNum],stackOfSign[topSign]);                    topNum--;                    topSign--;                }                else break;            }            if(s[p]!=')') stackOfSign[++topSign]=s[p];        }        p++;    }    while(topSign>0&&topNum>1)    {        stackOfNum[topNum-1]=cal(stackOfNum[topNum-1],stackOfNum[topNum],stackOfSign[topSign]);        topNum--;        topSign--;    }    return stackOfNum[topNum];}int main(){    memset(isTrue,true,sizeof(isTrue));    //先打个巨表~！    needPop['^']['^']=true;    needPop['^']['+']=false;    needPop['^']['-']=false;    needPop['^']['*']=false;    needPop['^']['/']=false;    needPop['^']['(']=false;    //----------------------    needPop['+']['^']=true;    needPop['+']['+']=true;    needPop['+']['-']=true;    needPop['+']['*']=true;    needPop['+']['/']=true;    needPop['+']['(']=false;    //----------------------    needPop['-']['^']=true;    needPop['-']['+']=true;    needPop['-']['-']=true;    needPop['-']['*']=true;    needPop['-']['/']=true;    needPop['-']['(']=false;    //----------------------    needPop['*']['^']=true;    needPop['*']['+']=false;    needPop['*']['-']=false;    needPop['*']['*']=true;    needPop['*']['/']=true;    needPop['*']['(']=false;    //----------------------    needPop['/']['^']=true;    needPop['/']['+']=false;    needPop['/']['-']=false;    needPop['/']['*']=true;    needPop['/']['/']=true;    needPop['/']['(']=false;    //----------------------    needPop['(']['^']=false;    needPop['(']['+']=false;    needPop['(']['-']=false;    needPop['(']['*']=false;    needPop['(']['/']=false;    needPop['(']['(']=false;    //----------------------    needPop[')']['^']=true;    needPop[')']['+']=true;    needPop[')']['-']=true;    needPop[')']['*']=true;    needPop[')']['/']=true;    needPop[')']['(']=true;    char s[MAXN];    int n;    long long trueAns1,trueAns2,nowAns1,nowAns2; //trueAns=带入a值后应该得到的答案，nowAns=选择选项中带入a值得到的答案    //scanf("%s",s+1);	gets(s+1);    trueAns1=getAns(s,strlen(s+1),1.4);    trueAns2=getAns(s,strlen(s+1),2.8);    scanf("%d",&n);	gets(s+1);    for(int i=0;i<n;i++)    {        //scanf("%s",s+1);		gets(s+1);		nowAns1=getAns(s,strlen(s+1),1.4);		nowAns2=getAns(s,strlen(s+1),2.8);        if(dcmp(trueAns1,nowAns1)!=0) //trueans==nowans            isTrue[i]=false;        if(dcmp(trueAns2,nowAns2)!=0) //trueans==nowans            isTrue[i]=false;    }    for(int i=0;i<n;i++)        if(isTrue[i])            printf("%c",'A'+i);    printf("\n");    return 0;}

[Codevs 1107][NOIP 1107]等价表达式