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で実装してたのでpairを使ってみた。
が無駄に長くなっただけだった。やはり複素数の計算には複素数を。