POJ 3295 Tautology(构造+模拟)

我不是女神ヾ 2022-05-17 01:50 144阅读 0赞

[题目链接][Link 1]

题目大意：给你一个字符串，含有p、q、r、s、t、K 、A、 N、C、E中的一些字符，这些大写字母代表一些运算符满足下表的运算方式，小写字母代表0或1，如果能找到至少一组小写字母的取值，使得这个式子为0，就输出"not"，否则输出"tautology"。

![70][]

分析：根据这个表，我们可以推出K代表&&逻辑运算符，其实因为这里面每个小写字母只能是0或1，所以也可以认为K是&，A代表||，也可以认为是|，N代表！，C代表（!a)|b，也可以认为是(!a)||b，E代表!(a^b)也可以是(a==b)，由于只有5个小写字母，且每个只能是0或者是1，那么也就是有2的5次方种情况，因为只有2的5次方种情况，所以可以直接暴力枚举每一种情况。

根据上面所推出的每种大写字母所表示的运算方式，发现其实只有单目运算符和双目运算符两种运算符，而单目运算符优先级又是高于双目运算符的，因此内层的运算总是在表达式末端，对于要求解这类嵌套表达式的值, 最好的数据结构就是栈，从最内层开始计算, 逐层向外推算。然后逆序遍历字符串：

1.  遇到逻辑变量，则把该逻辑变量的当前值(0或1)直接压入栈中
2.  遇到逻辑运算符, 则根据它是单目运算符还是双目运算符，从栈顶取出对应的两个逻辑变量或者是一个计算后, 将结果压入栈中。
3.  只要有一种情况使得表达式的值为0，就输出not，如果每种情况表达式的值都为1，就输出tautology。
4.      #include<map>
        #include<set>
        #include<cmath>
        #include<queue>
        #include<stack>
        #include<cstdio>
        #include<vector>
        #include<cctype>
        #include<cstring>
        #include<cstdlib>
        #include<iostream>
        #include<algorithm>
        #define inf 0x3f3f3f3f
        #define maxn 105
        #define Clear(x) memset(x,0,sizeof(x))
        #define fup(i,a,b) for(int i=a;i<b;i++)
        #define rfup(i,a,b) for(int i=a;i<=b;i++)
        #define fdn(i,a,b) for(int i=a;i>b;i--)
        #define rfdn(i,a,b) for(int i=a;i>=b;i--)
        typedef long long ll;
        using namespace std;
        const double pi=acos(-1.0);
        char str[maxn];
        
        int main()
        {
            int len,x,y;
            stack<int>Q;
            while(~scanf("%s",str)&&str[0]!='0')
            {
                int flag=1;
                while(!Q.empty()) Q.pop();
                len=strlen(str);
                for(int p=0;p<2;p++)
                    for(int q=0;q<2;q++)
                        for(int r=0;r<2;r++)
                            for(int s=0;s<2;s++)
                                for(int t=0;t<2;t++)
                                {
                                    for(int i=len-1;i>=0;i--)
                                    {
                                        if(str[i]=='p') Q.push(p);
                                        else if(str[i]=='q') Q.push(q);
                                        else if(str[i]=='r') Q.push(r);
                                        else if(str[i]=='s') Q.push(s);
                                        else if(str[i]=='t') Q.push(t);
                                        if(str[i]=='K'){
                                            x=Q.top();
                                            Q.pop();
                                            y=Q.top();
                                            Q.pop();
                                            Q.push(x&y);//Q.push(x&&y)也可以
                                        }else if(str[i]=='A'){
                                            x=Q.top();
                                            Q.pop();
                                            y=Q.top();
                                            Q.pop();
                                            Q.push(x|y);//Q.push(x||y)也可以
                                        }else if(str[i]=='N'){
                                            x=Q.top();
                                            Q.pop();
                                            Q.push(!x);
                                        }else if(str[i]=='C'){
                                            x=Q.top();
                                            Q.pop();
                                            y=Q.top();
                                            Q.pop();
                                            Q.push((!x)|y);//Q.push(!(x)||y)也可以
                                        }else if(str[i]=='E'){
                                            x=Q.top();
                                            Q.pop();
                                            y=Q.top();
                                            Q.pop();
                                            Q.push(!(x^y));
                                        }
                                    }
                                    if(Q.top()==0) flag=0;
                                }
                cout<<(flag?"tautology":"not")<<endl;
            }
            return 0;
        }

[Link 1]: http://poj.org/problem?id=3295
[70]: /images/20220517/3e175037953a41428e9f809fc6a7958c.png