题解 P1054 【等价表达式】

· · 题解

题面

现在拥有一些表达式，求出其中与原表达式等价的表达式。

分析

很容易想到暴力拆括号。但是，这个方法有2个麻烦的地方

  1. 需要实现一个储存因式的结构体并支持多种操作

  2. (a-1)^10^10^10^10等表达式会让结构体储存的东西多到爆炸。

所以，我们应该想到另一种方式判断。

可以想到，将一个值代入到表达式中，返回结果和基准一样就判对。

我使用的是后缀表达式计算和多值计算。

同时，注意一个坑：luogu中回车表示为\r\n，应当判断2次。

注意：在本题中有括号不匹配的数据，在计算的时候应该适当在左右添加括号以保证表达式括号匹配。

后缀表达式

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<stack>
using namespace std;
const long long M=1000000007;
struct Node{
    bool isnum;
    long long num;
    char ch;
    Node(bool isnum=false,long long num=0,char ch='\0'):isnum(isnum),num(num),ch(ch){}
};
stack<char> pri;
stack<long long> qwq;
char rd[60];
Node hz[30][60];
int ln[30],N;
bool isans[30];
long long powr(int O,int P){
    if(P<0) P+=M;
    long long ret=1,bas=O;
    while(P){
        if(P&1) ret=(ret*bas)%M;
        bas=(bas*bas)%M;
        P>>=1;
    }
    return ret;
}
int ope(char a){
    if(a=='-' || a=='+')    return 0;
    if(a=='*')  return 1;
    if(a=='^')  return 2;
    return -1;
}
void run(int bh){
    for(int i=0;rd[i];i++){
        if(rd[i]=='a')  hz[bh][ln[bh]++]=Node(true,-1,'\0');
        else if(rd[i]>='0' && rd[i]<='9'){
            long long ret=0;
            while(rd[i]>='0' && rd[i]<='9') ret=ret*10+rd[i]-'0',++i;
            --i;hz[bh][ln[bh]++]=Node(true,ret,'\0');
        }
        else if(rd[i]=='(') pri.push('(');
        else if(rd[i]==')'){
            while(!pri.empty() && pri.top()!='('){
                hz[bh][ln[bh]++]=Node(false,0,pri.top());
                pri.pop();
            }
            if(!pri.empty())    pri.pop();
        }
        else{
            while(!pri.empty() && ope(pri.top())>=ope(rd[i])){
                hz[bh][ln[bh]++]=Node(false,0,pri.top());
                pri.pop();
            }
            pri.push(rd[i]);
        }
    }
    while(!pri.empty()){
        if(pri.top()!='(')  hz[bh][ln[bh]++]=Node(false,0,pri.top());
        pri.pop();
    }
    while(!pri.empty()){
        hz[bh][ln[bh]++]=Node(false,0,pri.top());
        pri.pop();
    }
}
void rdl(){
    char a;
    memset(rd,0,sizeof(rd));
    int len=0;
    while(scanf("%c",&a) && a!='\n' && a!='\r'){
        if(a!=' ')  rd[len++]=a;
    }
    scanf("%c",&a);
}
long long mans(int bh,int A){
    for(int i=0;i<ln[bh];i++){
        if(hz[bh][i].isnum){
            if(hz[bh][i].num==-1LL) qwq.push(1LL*A);
            else    qwq.push(hz[bh][i].num);
        }
        else{
            long long B=qwq.top();qwq.pop();
            long long C=qwq.top();qwq.pop();
            if(hz[bh][i].ch=='+')   qwq.push((C+B)%M);
            if(hz[bh][i].ch=='-')   qwq.push((C-B+M)%M);
            if(hz[bh][i].ch=='*')   qwq.push((C*B)%M);
            if(hz[bh][i].ch=='^')   qwq.push(powr(C,B));
        }
    }
    long long ret=qwq.top();qwq.pop();
    return ret;
}
int main(){
    srand(15608*1234+545);
    rdl();
    run(0);
    scanf("%d%*c%*c",&N);
    for(int i=1;i<=N;i++){
        rdl();
        run(i);
    }
    for(int i=1;i<=10;i++){
        int A=rand();
        long long ans=mans(0,A);
        for(int i=1;i<=N;i++){
            if(mans(i,A)!=ans)  isans[i]=true;
        }
    }
    for(int i=1;i<=N;i++)
        if(!isans[i])   printf("%c",i-1+'A');
}