题解 P1054 【等价表达式】

totorato · 2017-10-20 16:39:42 · 题解

利用树形结构递归求解

首先：如果两个表达式在自变量相等时，取值始终相等，则我们认为这两个表达式是等价的。

所以我们只需要分别计算每个表达式在a取某些数时的值，判断是否都与第一个表达式相等即可。

由于取值可能较大，计算时需要取模。

其次：中缀表达式求值时优先级最低的符号会最后计算。

所以我们可以递归计算优先级最低的符号左右两边的算式，最后合并。

所以我们可以得到如下的代码

#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 55
#define oo 10020123
#define MD 100000007

using namespace std;

typedef long long ll;

ll qpw(ll x,ll t){ll ans=1;for(int i=1;i<=t;i++)ans=ans*x%MD;return ans;}

ll calc(char *str,int l,int r,ll a)
{
    int prio=0,mnpos=MX,mn=+oo,cnt=0,p[MX],num=0;
    memset(p,0x3f,sizeof(p));
    for(int i=r;i>=l;i--)
    {
        if(str[i]==')')prio+=100;
        if(str[i]=='(')prio-=100;
        if(str[i]=='^')p[i]=prio+3,cnt++;
        if(str[i]=='*')p[i]=prio+2,cnt++;
        if(str[i]=='+')p[i]=prio+1,cnt++;
        if(str[i]=='-')p[i]=prio+1,cnt++;
        if(mn>p[i])mn=p[i],mnpos=i;
    }
    if(cnt==0)
    {
        for(int i=l;i<=r;i++)if(str[i]=='a')return a;
        for(int i=l;i<=r;i++)if(isdigit(str[i]))num=num*10+str[i]-'0';
        return num;
    }
    else
    {
        if(str[mnpos]=='^')return qpw(calc(str,l,mnpos-1,a),calc(str,mnpos+1,r,a));
        if(str[mnpos]=='*')return (calc(str,l,mnpos-1,a)*calc(str,mnpos+1,r,a))%MD;
        if(str[mnpos]=='+')return (calc(str,l,mnpos-1,a)+calc(str,mnpos+1,r,a))%MD;
        if(str[mnpos]=='-')return (calc(str,l,mnpos-1,a)-calc(str,mnpos+1,r,a))%MD;
    }
    return 0;
}

int main()
{
    int len[27],n,ans[15];
    char str[27][MX];    
    scanf("%[^\r]",str[0]),getchar();
    len[0]=strlen(str[0]);
    scanf("%d",&n),getchar();
    for(int i=1;i<=n;i++)
    {
        scanf("%[^\r]",str[i]),getchar();
        len[i]=strlen(str[i]);
    }
    for(int i=0;i<=10;i++)ans[i]=calc(str[0],0,len[0]-1,i-5);
    for(int i=1;i<=n;i++)
    {
        int f=1;
        for(int j=0;j<=10;j++)
            if(ans[j]!=calc(str[i],0,len[i]-1,j-5))
                {f=0;break;}
        if(f)printf("%c",'A'+i-1);
    }
    return 0;
}