AOJ 1102 Calculation of Expressions
以前ドはまりして5WAくらい貰った問題。
今回も5WAしてジャッジデータ持ってきてバグ塞いで漸くAC.
出典
ACM International Collegiate Programming Contest Japan Domestic, 1998
問題概要
与えられた+,-,*,(,)と整数、iを含む複素数の式を計算し、計算結果を表示せよ。
計算の途中で絶対値が10000を超える整数が現れた場合overflowと表示せよ。
出力する式は以下の形式を満たす必要がある。
- 0(結果が0+0i)
- -123 (結果が-123+0i)
- 45i(結果が0+45i)
- 3+1i(結果が3+i)
- 123-45i(結果が123-45i)
解法
構文解析を実装する……んだけど異様にハマりポイントが多かった。
や、他の人は普通に解いているので僕がアホなだけかもしれない。
以下やってしまったミス
- 単項演算子+の処理忘れ
- 1iをiと出力
- 10000以上でoverflow
- 32bitintを超える入力値でoverflow検出ミス(プログラム内でオーバーフローしてどうする!)
など。バグが複数入り混じるとほんと何が原因だかわからなくなる……どうしたらいいのだろう。
以下やたらスパゲティなソース
bool of=0; string expr; void ck(pi a) { if(abs(a.first)>10000||abs(a.second)>10000) of=1; } pi add(pi a,pi b,char op) { ck(a),ck(b); pi ret; ret.first=a.first+(op=='+'?b.first:-b.first); ret.second=a.second+(op=='+'?b.second:-b.second); ck(ret); return ret; } pi mul(pi x,pi y) { ck(x),ck(y); int a=x.first,b=x.second,c=y.first,d=y.second; pi ret=mp(a*c-b*d,a*d+b*c); ck(ret); return ret; } pi eval(int s,int t) { int p=t-1,d=0;//左結合なので右から演算子を探していく for(;p>s;p--) { char c=expr[p]; if(c=='(')d++; if(c==')')d--; if(d==0&&(c=='+'||c=='-'))break; } //単項 if(p==s) { if(expr[s]=='-') { pi ret=eval(s+1,t); ret.first*=-1,ret.second*=-1; return ret; } if(expr[s]=='+')return eval(s+1,t); for(p=t-1,d=0;p>s;p--) { char c=expr[p]; if(c=='(')d++; if(c==')')d--; if(d==0&&c=='*')break; } //単因数 if(p==s) { if(expr[s]=='(')return eval(s+1,t-1); if(expr[s]=='i')return mp(0,1); int n=0; for(int i=s;i<t;i++) { n*=10,n+=expr[i]-'0'; if(n>10000)of=1; } return mp(n,0); } //複数因数 return mul(eval(s,p),eval(p+1,t)); } //複数項 return add(eval(s,p),eval(p+1,t),expr[p]); } int main() { while(getline(cin,expr)) { of=0; pi ans=eval(0,expr.size()); if(of)cout<<"overflow"<<endl; else { int a=ans.first,b=ans.second; if(a==0&&b==0)cout<<0<<endl; else if(a==0) cout<<b<<"i"<<endl; else if(b==0)cout<<a<<endl; else if(b>0)cout<<a<<"+"<<b<<"i"<<endl; else cout<<a<<b<<"i"<<endl; } } return 0; }
昔やったWAった時はcomplex
が無駄に長くなっただけだった。やはり複素数の計算には複素数を。