PKU 1686 Lazy Math Instructor
http://poj.org/problem?id=1686
二つの式が与えられるので、その式が等しいかどうかを確かめるという問題。
久しぶりに、それなりの問題が解けたような気がします。
構文解析部分は殆どhttp://d.hatena.ne.jp/atetubou/20110317/1300367965と一緒です。
タブとか空白が勝手に出現するという条件を見逃して1WA。
詰んだかと思いました。
mapの比較では値に0を持つものとkeyが存在しないものはイコールにならないので、そこらへんを調整しています。多倍長とかが出てくるほど鬼畜な問題じゃなくて本当に良かった。
typedef map<string,int> ex; string in; int pos=0; ex operator+(const ex&l,const ex&r){ ex ret; FOR(miter,l)ret[miter->F]+=miter->S; FOR(miter,r)ret[miter->F]+=miter->S; return ret; } ex operator-(const ex&l,const ex&r){ ex ret; FOR(miter,l)ret[miter->F]+=miter->S; FOR(miter,r)ret[miter->F]-=miter->S; return ret; } ex operator*(const ex&l,const ex&r){ ex ret; FOR(liter,l) FOR(riter,r){ string tt=liter->F+riter->F; sort(ALL(tt)); ret[tt]+=liter->S*riter->S; } return ret; } ex getnum(){ ex ret; if(isdigit(in[pos])){ ret[""]=in[pos++]-'0'; }else{ string tt; tt+=in[pos++]; ret[tt]=1; } return ret; } ex expr(){ ex ret; if(in[pos]=='('){ ++pos; ret=expr(); }else{ ret=getnum(); } deque<ex> st; st.pb(ret); deque<char> op; while(pos<in.size() && in[pos]!=')'){ char cop=in[pos]; ++pos; ex tt; if(in[pos]=='('){ ++pos; tt=expr(); }else tt=getnum(); switch(cop){ case '+': op.pb(cop); st.pb(tt); break; case '-': op.pb(cop); st.pb(tt); break; case '*': ret=st.back()*tt; st.pop_back(); st.pb(ret); break; } } ret=st.front();st.pop_front(); while(!st.empty()){ char cop=op.front();op.pop_front(); ex tt=st.front();st.pop_front(); if(cop=='+')ret=ret+tt; else ret=ret-tt; } ++pos; return ret; } main(){ int n; cin>>n; cin.ignore(); while(n--){ ex a,b; string tt; getline(cin,tt); in=""; rep(i,tt.size())if(tt[i]!=' ' && tt[i]!='\t')in+=tt[i]; pos=0; a=expr(); getline(cin,tt); in=""; rep(i,tt.size())if(tt[i]!=' ' && tt[i]!='\t')in+=tt[i]; pos=0; b=expr(); set<string> app; FOR(aiter,a)app.insert(aiter->F); FOR(biter,b)app.insert(biter->F); FOR(siter,app){ a[*siter]*=1; b[*siter]*=1; } if(a==b)cout<<"YES"<<endl; else cout<<"NO"<<endl; } }