题解 P1054 【等价表达式】

· · 题解

这题倒不是说多么难…但是…真的很多细节啊QwQ...看见楼下refun RE了 宝宝十分开心（？？？） 于是来发啦。。（话说我就用的gets...）

数据里有一些奇奇怪怪的点（？？？） 括号是不匹配的 这就需要我们在考虑括号的时候更全面 来应对不配对的情况 希望管理员能改一下啦 解救广大劳苦人民…掉坑n次

为了防止出现负数 在计算之后%质数时要先加上质数本身

注释写的很详细了

以下代码

#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
char w[55],c[55];
int n,x,t1,t2,a[100];
long long check[5],c1[55],c2[55],c3[55];//用三个质数作为特殊值
int pow(int a,int b)
{
    int s=a;
    for (int i=2;i<=b;i++) s=(s*a+10007)%10007; 
    return s;
}
void ys()
{
    int m1=c1[t2],n1=c1[t2-1],m2=c2[t2],n2=c2[t2-1],m3=c3[t2],n3=c3[--t2]; 
    switch(w[t1])//同时对三个特殊值进行运算 数字栈为别为c1 c2 c3 符号栈为相同的w栈 
    {
        case '+':c1[t2]=(n1+m1+10007)%10007; c2[t2]=(n2+m2+10007)%10007; c3[t2]=(n3+m3+10007)%10007; break;
        case '-':c1[t2]=(n1-m1+10007)%10007; c2[t2]=(n2-m2+10007)%10007; c3[t2]=(n3-m3+10007)%10007; break;
        case '*':c1[t2]=(n1*m1+10007)%10007; c2[t2]=(n2*m2+10007)%10007; c3[t2]=(n3*m3+10007)%10007; break;
        case '^':c1[t2]=pow(n1,m1); c2[t2]=pow(n2,m2); c3[t2]=pow(n3,m3); break;
    }
    t1--;//运算完毕后运算符出栈 
}
void js()
{
    x=0;
    for (int i=0;i<strlen(c);i++)
    {
        if (c[i]=='a') {c1[++t2]=3; c2[t2]=7; c3[t2]=13;} //是变量直接进栈
        else if (c[i]>='0'&&c[i]<='9') x=x*10+c[i]-48;//可能有多位数字出现 在出现符号前进行累加 
        else//是字符进行处理 
        {
            if (x!=0) {c1[++t2]=x; c2[t2]=x; c3[t2]=x; x=0;}
            if (a[c[i]]==0) continue;
            if (c[i]=='('||t1==0&&c[i]!=')') w[++t1]=c[i]; 
            else 
                if (a[c[i]]<a[w[t1]])//当前读入字符优先级高 
                    if (c[i]!=')') w[++t1]=c[i]; else//不是右括号则进栈 若读进右括号要进行计算 
                    {
                        while (w[t1]!='('&&t1>0) ys();//计算到左括号停止    
                        if (w[t1]=='(') t1--;//左括号出栈 
                    }
                else//当前读入字符优先级低 
                {
                    while (a[c[i]]>=a[w[t1]]&&t1>0) ys();//将比当前字符优先级低的都计算完 
                    if (c[i]!=')') w[++t1]=c[i];//读入的字符进栈 
                }
        }
    }
    if (x!=0) {c1[++t2]=x; c2[t2]=x; c3[t2]=x; x=0;}
    while (t1>0) ys();//将栈中剩下的同级运算符都做完 
}
int main()
{
//    freopen("equal.in","r",stdin);
//    freopen("equal.out","w",stdout);
    a[40]=5; a[41]=1; a[94]=2; a[42]=a[47]=3; a[43]=a[45]=4;//设置各符号的优先级 数值越小优先级越高 
    gets(c); scanf("%d",&n); js(); gets(c);
    check[1]=c1[1]; check[2]=c2[1]; check[3]=c3[1];//以题干代数式得到的三个值为标准check 
    for (int i=1;i<=n;i++) 
    {
        t1=t2=0; gets(c); js(); 
        if (check[1]==c1[1]%10007&&check[2]==c2[1]%10007&&check[3]==c3[1]%10007) 
            printf("%c",i+64);//若三个质数运算得到的结果与标准相同则输出编号 
    }
    fclose(stdin); fclose(stdout);
    return 0;
}