P1054 等价表达式

· · 题解

思路：特殊值法

假设a为某个值。将a带入题干式中得出一个值jizhun，并将a的值代入每一个选项式中得到一个值ans。

若ans=jizhun，则该选项式式等价于题干式。 这样做的出错几率极低（尤其是当a的代入值较大时）。

Code:

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

const int MAXN=105;
const long long MOD=1000000007,uni=100000007;
//注意uni的值（即a）不要取得过大（否则会爆long long） 
int n,first[MAXN];

int len;
char ss[MAXN];

int totc;
char charac[MAXN];

int cnt;
char last[MAXN];
int num,now,totl;
long long shu[MAXN],lnum[MAXN],jizhun,ans;

bool book[MAXN];

void read()//手动读字符串
{
    char ch=getchar();
    while(1)
    {
        if(ch=='\n')//过滤掉回车 
        {
            return;
        }
        if(ch==' ')  ch=getchar();//过滤掉空格       
        if(ch!=' ')
        {
            ss[++len]=ch;
            ch=getchar();
        }
    }
}

void clean()//注意随时清空 
{
    for(int i=1;i<=num;i++)  shu[i]=0;
    totc=0,totl=0,cnt=0,num=0,ans=0,now=0,len=0,lnum[1]=0;
}

int find(int x)//将中缀表达式中的多位数的字符串形式转为数。 
{
    num++;
    int tmp=0;
    while('0'<=ss[x]&&ss[x]<='9')
    {
        shu[num]=((shu[num]*10)%MOD+(ss[x]-'0')+MOD)%MOD;
        x++,tmp++;
    }
    return tmp;
}

void query()//后缀表达式求式子的值 
{
    for(int i=1;i<=cnt;i++)
    {
        if(last[i]=='0')    lnum[++totl]=shu[++now];
        if(last[i]=='a')    lnum[++totl]=uni;
        if(last[i]!='0'&&last[i]!='a')
        {
            if(last[i]=='+')    lnum[totl-1]=(lnum[totl-1]+lnum[totl]+MOD)%MOD;
            if(last[i]=='-')    lnum[totl-1]=(lnum[totl-1]-lnum[totl]+MOD)%MOD;
            //注意减号的模运算法则是(a-b)%MOD=((a%MOD)-(b%MOD)+MOD)%MOD; 
            if(last[i]=='*')    lnum[totl-1]=(lnum[totl-1]*lnum[totl]+MOD)%MOD;
            if(last[i]=='^')
            {
                long long tmp=lnum[totl-1];
                for(int j=1;j<=lnum[totl]-1;j++)    lnum[totl-1]=(lnum[totl-1]*tmp)%MOD;
            }
            totl--;
        }
    }

    ans=lnum[1];
}

void work()//中缀转后缀 
{
    clean();
    read();

    int i=1;
    while(i<=len)
    {
        if(ss[i]=='a')  last[++cnt]=ss[i];

        if('0'<=ss[i]&&ss[i]<='9')
        {
            last[++cnt]='0';
            i+=find(i);continue;
        }

        if(ss[i]=='+'||ss[i]=='-'||ss[i]=='*'||ss[i]=='^')
        {
            while(first[(int)charac[totc]]>=first[(int)ss[i]]&&totc>0&&charac[totc]!='(')
            {
                last[++cnt]=charac[totc];
                totc--;
            }
            charac[++totc]=ss[i];
        }

        if(ss[i]=='(')  charac[++totc]=ss[i];

        if(ss[i]==')')  
        {
            while(charac[totc]!='('&&totc>0)
            {
                last[++cnt]=charac[totc];
                totc--;             
            }
            totc--;
        }
        i++;
    }
    for(int i=totc;i>=1;i--)    last[++cnt]=charac[i];
}

int main()
{   
    first[(int)'(']=3,first[(int)')']=3,first[(int)'^']=3;
    first[(int)'*']=2,first[(int)'+']=1,first[(int)'-']=1;

    work();query();
    jizhun=ans;

    scanf("%d",&n);
    //注意：这个n读入后会随之来一个'\n'，实际读时会把当成一个字符串，然后它的ans会调用文本串的lnum[1] 
    n+=1;//注意：这个n读入后会随之来一个'\n'，实际读时会把当成一个字符串，所以总的字符串读入个数为n+1. 
    for(int i=1;i<=n;i++)
    {
        work();query();
        if(ans==jizhun) book[i]=1;
    }
    for(int i=1;i<=n;i++)   
        if(book[i]==1)  cout<<(char)(64+i-1);//n读入后的'\n'实际读时会把当成一个字符串,所以判掉。 

    return 0;
}