题解 P1054 【等价表达式】

· · 题解

这道题并不难，主要有几个比较坑的地方

首先，最好不要用gets，因为经常会出问题

其次，本题括号有可能不匹配，所以我们在找答案时，先判断括号匹不匹配，如果不匹配，就直接舍去。

还有可以把a代入一个值，随便搞一下，我代入了1231这个值（并不是只能用这个）

中间结果和最后结果都很大，需要mod一个数，我mod了1000000007

最后，计算表达式时，采用分治法，找到最后一个计算的符号，分别计算两边的值，通过这个符号合起来。我的计算写了两遍，一个算最开始的那个表达式，一个算预选的答案的表达式的值，代码会比较长。

附代码（仅供参考，请不要抄袭，建议只看上述文字，自行编程解决）

#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int mod=1000000007,a=1231;
int n,l[30],x,la;
char s[30][100],c,p[100];
int Pow(int x,int y){//算次幂
    long long a=1;
    for (int i=0;i<y;i++)
    a=a*x%mod;
    return a;
}
int js1(int b,int e){
    int t=0,a,bb,c;a=bb=c=-1;
    for (int i=b;i<=e;i++)
    {
        if (p[i]<'0' || p[i]>'9')break;
        t=t*10+p[i]-'0';
        if (i==e)return t;
    }
    t=0;
    for (int i=b;i<=e;i++)
    {
        if (p[i]=='(')t++;
        if (p[i]==')')t--;
        if (!t)
        {
            if (p[i]=='+' || p[i]=='-')a=i;
            if (p[i]=='*')bb=i;
            if (p[i]=='^')c=i;

}//找到最后一个计算的符号，切记，不能再括号里！

    }
    if (a!=-1)
    {
        if (p[a]=='+')
        return (((long long)js1(b,a-1)+js1(a+1,e))%mod+mod)%mod;
        else
        return (((long long)js1(b,a-1)-js1(a+1,e))%mod+mod)%mod;
    }
    if (bb!=-1)
    return (((long long)js1(b,bb-1)*js1(bb+1,e))%mod+mod)%mod;
    if (c!=-1)
    return (Pow(js1(b,c-1),js1(c+1,e))%mod+mod)%mod;
    return js1(b+1,e-1);//没有最后一个符号，说明这个表达式被括号裹在里面，要去掉括号
}
bool kuohao(int x){
    int h=0;
    for (int i=0;i<l[x];i++)
    {
        if (s[x][i]=='(')h++;
        if (s[x][i]==')')h--;
        if (h<0)return false;
    }
    return !h;
}
int js(int x,int b,int e){
    int t=0,a,bb,c;a=bb=c=-1;
    for (int i=b;i<=e;i++)
    {
        if (s[x][i]<'0' || s[x][i]>'9')break;
        t=t*10+s[x][i]-'0';
        if (i==e)return t;
    }
    t=0;
    for (int i=b;i<=e;i++)
    {
        if (s[x][i]=='(')t++;
        if (s[x][i]==')')t--;
        if (!t)
        {
            if (s[x][i]=='+' || s[x][i]=='-')a=i;
            if (s[x][i]=='*')bb=i;
            if (s[x][i]=='^')c=i;
        }
    }
    if (a!=-1)
    {
        if (s[x][a]=='+')
        return (((long long)js(x,b,a-1)+js(x,a+1,e))%mod+mod)%mod;
        else
        return (((long long)js(x,b,a-1)-js(x,a+1,e))%mod+mod)%mod;
    }
    if (bb!=-1)
    return (((long long)js(x,b,bb-1)*js(x,bb+1,e))%mod+mod)%mod;
    if (c!=-1)
    return (Pow(js(x,b,c-1),js(x,c+1,e))%mod+mod)%mod;
    return js(x,b+1,e-1);
}
int main()
{
    c=getchar();
    while(c!='\n' && c!='\r')
    {
        if (c!=' ')
        {
            if (c!='a')
            p[la++]=c;
            else
            {
                p[la++]='1';
                p[la++]='2';
                p[la++]='3';
                p[la++]='1';
            }
        }
        c=getchar();
    }
    scanf("%d",&n);
    for (;x<n;x++)
    {
        c=getchar();
        while(c=='\n' || c=='\r')
        c=getchar();
        while(c!='\n' && c!='\r')
        {
            if (c!=' ')
            {
                if (c!='a')
                s[x][l[x]++]=c;
                else
                {
                    s[x][l[x]++]='1';
                    s[x][l[x]++]='2';
                    s[x][l[x]++]='3';
                    s[x][l[x]++]='1';
                }
            }
            c=getchar();
        }
    }
    int hhh=js1(0,la-1);
    for (int i=0;i<n;i++)
    if (kuohao(i) && js(i,0,l[i]-1)==hhh)
    printf("%c",'A'+i);
    return 0;
}