pku 3295 Tautology(枚举+递归)

#include<iostream> #include<string> using namespace std; bool solve(string& WFF); string WFF; bool state[5]; int main() { bool flag; while(cin>>WFF) { if(WFF[0]=='0') return 0; flag=true; for(int i=0;i<=0x1f;i++)//用位运算枚举 p q r s t各种可能的值 { for(int j=0;j<5;j++) { state[j]=(i>>j)&1; } if(solve(WFF)==false) { flag=false; break; } } if(flag) printf("tautology/n"); else printf("not/n"); } } bool solve(string& WFF) { string s1,s2; int len=WFF.length(); if(len==1) return state[WFF[0]-'p']; if(WFF[0]=='N') { s1=WFF.substr(1,len-1); return !solve(s1); } int a=0,b=0;//a记录变量的数量 b记录运算符的数量 for(int i=1;;i++) { if(a<=b)//分解串，当a-b==1说明得到了第一个子串 { if('p'<=WFF[i]&&WFF[i]<='t') { a++; } else if(WFF[i]!='N') b++; } else { s1=WFF.substr(1,i-1);//递归得到子串的值，然后进行运算 s2=WFF.substr(i,len-i); bool m=solve(s1),n=solve(s2); if(WFF[0]=='K') return m&&n; if(WFF[0]=='A') return m||n; if(WFF[0]=='C') return (!m)||(m&&n); if(WFF[0]=='E') return !(m^n); } } }