PKU 3295 Tautology
http://poj.org/problem?id=3295
論理式の変数を変えて、その論理式が常に1になるものなのかどうかを判定しろというような問題。
簡易的な構文解析と全探索。
Eをxorで計算して1WA。
string in; int pos; bool ctob[128]; bool get(){ if(islower(in[pos])){ return ctob[in[pos++]]; } bool wfr,wfl; switch(in[pos++]){ case 'K': return get()&get(); case 'A': return get()|get(); case 'N': return !get(); case 'C': wfl=get(); wfr=get(); if(wfl && !wfr)return false; return true; case 'E': return get()==get(); } } string val="pqrst"; main(){ while(cin>>in,in!="0"){ bool ok=true; rep(i,1<<5){ rep(j,5){ if((i>>j)&1)ctob[val[j]]=true; else ctob[val[j]]=false; } pos=0; if(!get()){ ok=false; break; } } if(ok)cout<<"tautology"<<endl; else cout<<"not"<<endl; } }