题意: 给定一个命题公式,判断该式子是否为永真式. 因为最多只有 5 5 5个变量,所以一共 32 32 32种情况, 然后可以从后往前处理表达式的真值,所有情况都返回真就是真,否则就是假.
#include<iostream> #include<string> #include<cstdio> #include<stack> using namespace std; int a[32][5]; int main(){ ios::sync_with_stdio(false),cin.tie(0); string s; for(int i=0;i<32;i++) for(int j=0;j<5;j++) a[i][j]=((i>>j)&1); while(cin>>s&&s!="0"){ int n=s.size(); int st[205]={},top=0; bool ok=1; for(int k=0;k<32;k++){ st[0]=top=0; //注意初始化 for(int i=n-1;~i;i--){ if(s[i]>='p'&&s[i]<='t') st[top++]=a[k][s[i]-'p']; else if(s[i]=='K') st[top-2]=(st[top-2]&st[top-1]),top--; else if(s[i]=='A') st[top-2]=(st[top-2]|st[top-1]),top--; else if(s[i]=='N') st[top-1]=!st[top-1]; else if(s[i]=='C') st[top-2]=(!st[top-2]|st[top-1]),top--; else if(s[i]=='E') st[top-2]=st[top-2]==st[top-1],top--; } if(st[0]==0){ ok=0;break; } } if(ok) cout<<"tautology"<<'\n'; else cout<<"not"<<'\n'; } }总结 : 对于后缀表达式,命题公式这样类型的式子往往是栈类型的处理方式解决问题.