题解 P1054 【等价表达式】

wumingshi · 2016-11-09 18:36:30 · 题解

首先，我只想说：这道题太恶心了！

第一，这道题存在左、右括号不匹配的情况。

第二，gets在洛谷可能是不能正常使用的。//感谢楼下的快读

第三，当我们将字符a代入之后，由于答案会爆long long，所以需要取模。然而当我们在做减法的时候，由于我们已经进行了模运算，所以两个余数的大小是未知的，于是我们要在减后加上取模的那个数（我用的1e9+7），然后再取模，这样就不会出现负数的情况了。

附上自己乱搞的代码：

#include<cstdio>
#include<cstring>
#define LL long long
const int M=1e9+7;
LL n,i,p,topn,topf,len,k;
char a[51];
LL num[51];
char f[51];
LL t[11]={0,41,71,83,91,101};
LL ans[11];
char c[51];
LL quickpow(LL a,LL b,LL p)
{
    LL s=1;
    a%=p;
    for(;b;b>>=1,a=(a*a)%p)
      if(b&1) s=(s*a)%p;
    return s;
}
LL level(char c)
{
    if(c=='(') return 0;
    if(c=='+'||c=='-') return 1;
    if(c=='*'||c=='/') return 2;
    if(c=='^') return 3;
    return 0;
}
void work()
{
    LL x=num[topn--];
    LL y=num[topn--];
    char c=f[topf--];
    if(c=='+') num[++topn]=(x+y)%M;
    else if(c=='-') num[++topn]=(y-x+M)%M;//注意＋M
    else if(c=='*') num[++topn]=(x*y)%M;
    else if(c=='^') num[++topn]=quickpow(y,x,M);
}
void getnum(char a[],LL &p)
{
    LL t=0;
    while(a[p]>='0'&&a[p]<='9') 
      t=(t*10+a[p++]-48)%M;
    num[++topn]=t;
}
void push(LL n)//将字符a用第n个数进行替换
{
    num[++topn]=t[n];
}
LL solve(char a[],LL i)
{
    p=topf=topn=0;
    len=strlen(a);
    while(p<=len-1)
      if(a[p]>='0'&&a[p]<='9') getnum(a,p);
      else if(a[p]==' ') p++;
      else if(a[p]=='+'||a[p]=='-'||a[p]=='*'||a[p]=='/'||a[p]=='^')
             if(level(a[p])>level(f[topf])) f[++topf]=a[p++];
             else
             {
                   while(level(a[p])<=level(f[topf])) work();
                   f[++topf]=a[p++];
                }
      else if(a[p]=='a')
      {
        push(i);
        p++;
      }
      else if(a[p]=='(') f[++topf]=a[p++];
      else if(a[p]==')')
      {
          bool bb=0;
          for(int i=1;i<=topf;i++)
            if(f[i]=='(') bb=1;
          if(!bb)
          {
              p++;
              continue;
          }
        while(f[topf]!='(')
          work();
        topf--;
        p++;
      }
    while(topn!=1) work();//我的程序在运行后会出现未计算完的情况
    return num[1];
}
void get(char a[])
{
    for(int i=0;i<=50;i++)
      a[i]='\0';
    char c=getchar();
    int pos=0;
    while(c=='\n'||c=='\r') c=getchar();
    while(c!='\n'&&c!='\r')
    {
        a[pos++]=c;
        c=getchar();
    }
}
int main()
{
    freopen("equal.in","r",stdin);
    freopen("equal.out","w",stdout);
    get(a);
    for(i=1;i<=5;i++)
      ans[i]=solve(a,i);
    scanf("%I64d\n",&n);
    for(k=1;k<=n;k++)
    {
        get(c);
        bool b=1;
        for(i=1;i<=5;i++)
          if(solve(c,i)!=ans[i])
          {
              b=0;
              break;
          }
        if(b) putchar('A'+k-1);
    }
}