AOJ 1102 Calculation of Expressions
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1102
構文解析する問題。
以下のようなEBNF構文的なものを書いてから実装してみた。
1iをiと出力するのだと勘違いしていた。
expression:= {'('},(expression|num),{op,(expression|num)},{')'}
num:='i'|digit
op:='+'|'-'|'*'
string in; int pos; bool over; void check(PI&p){ over|=p.F>10000 || p.S>10000 || p.F<-10000 || p.S<-10000; } PI operator*(const PI&l,const PI&r){ PI ret=mp(l.F*r.S+r.F*l.S,l.S*r.S-l.F*r.F); check(ret); return ret; } PI operator+(const PI&l,const PI&r){ PI ret=mp(l.F+r.F,l.S+r.S); check(ret); return ret; } PI operator-(const PI&l,const PI&r){ PI ret=mp(l.F-r.F,l.S-r.S); check(ret); return ret; } void pr(const PI&ans){ if(over)cout<<"overflow"<<endl; else{ if(ans.S){ cout<<ans.S; if(ans.F>0)cout<<'+'; } if(ans.F){ cout<<ans.F<<'i'; } if(ans.F==0 && ans.S==0)cout<<0; cout<<endl; } } PI getnum(){ if(in[pos]=='i'){ ++pos; return mp(1,0); } PI ret=mp(0,0); while(pos<in.size() && isdigit(in[pos])){ ret.S=ret.S*10+in[pos++]-'0'; check(ret); } return ret; } PI expr(){ PI ret; if(in[pos]=='('){ ++pos; ret=expr(); }else{ ret=getnum(); } deque<PI> st; st.pb(ret); deque<char> op; while(pos<in.size() && in[pos]!=')'){ char cop=in[pos]; ++pos; PI 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(); PI tt=st.front();st.pop_front(); if(cop=='+')ret=ret+tt; else ret=ret-tt; } ++pos; return ret; } main(){ while(cin>>in){ over=pos=0; PI ans=expr(); check(ans); pr(ans); } }