UVa 11954 Binary Calculator
http://uva.onlinejudge.org/contests/279-c0158285/11954.html
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=229&page=show_problem&problem=3105 (現在問題が見えなていないので上のリンクを見てください)
昨日の復習。構文解析する問題。
与えられた構文ルールが微妙なせいで、逆に分かりにくくなっている気がします。素直にやろうとしたら優先順位とかで死にまくっていたようです。コンテスト中に解きたかったなと思いました。
string in; int pos; string number(){ string ret; while(pos<SZ(in) && isdigit(in[pos]))ret+=in[pos++]; while(SZ(ret)>1 && ret[0]=='0')ret=ret.substr(1); return ret; } string token(){ string ret; if(isdigit(in[pos]))return number(); string op=in.substr(pos,3); pos+=3; ret=token(); if(op=="not"){ rep(i,SZ(ret)){ if(ret[i]=='0')ret[i]='1'; else ret[i]='0'; } }else if(op=="shr"){ if(SZ(ret)>1)ret=ret.substr(0,SZ(ret)-1); else ret="0"; }else{ ret+='0'; while(SZ(ret)>1 && ret[0]=='0')ret=ret.substr(1); } while(SZ(ret)>1 && ret[0]=='0')ret=ret.substr(1); return ret; } string expression(){ string ret=token(); string li; while(pos<in.size()){ li=ret; ret=""; string op; if(in[pos]!='o'){ op=in.substr(pos,3); pos+=3; }else{ op=in.substr(pos,2); pos+=2; } string ri=token(); int sz=max(SZ(li),SZ(ri)); while(SZ(ri)<sz)ri='0'+ri; while(SZ(li)<sz)li='0'+li; if(op=="or"){ rep(i,SZ(li)){ if(li[i]=='1' || ri[i]=='1')ret+='1'; else ret+='0'; } }else if(op=="and"){ rep(i,SZ(li)){ if(li[i]=='1' && ri[i]=='1')ret+='1'; else ret+='0'; } }else{ rep(i,SZ(li)){ if(li[i]+ri[i]-2*'0'==1)ret+='1'; else ret+='0'; } } } while(SZ(ret)>1 && ret[0]=='0')ret=ret.substr(1); return ret; } main(){ int test; cin>>test; cin.ignore(); rep(ca,test){ cout<<"Case "<<ca+1<<": "; string temp; getline(cin,temp); in=""; pos=0; rep(i,SZ(temp))if(temp[i]!=' ')in+=temp[i]; string ans=expression(); cout<<ans<<endl; } }