ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1102 Calculation of Expressions

問題文はこちら↓
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1102


・概要
以下のような感じです。
・演算(加算、減算、乗算)と虚数を含む式
・計算途中で実数、または虚数の値の絶対値が10000を超えたらoverflow


・解法
構文解析をします。

実数と虚数を分けて考えなければいけないので、
pair<実数, 虚数>のようにして値を渡してあげればよいです。

BNFはおそらく以下のような感じです。
::= '+' | '-' |
::= '*' |
::= | number | 'i'

もしかしたらもっとよいやり方があるかも知れません。


ソースコード

#include<iostream>
#include<map>
#include<string>
#include<cctype>
using namespace std;

#define f first
#define s second
#define mp make_pair
#define OVERFLOW mp(INF,INF)
typedef pair<int,int> P;
static const int INF = (1 << 29);

string s;
int pos;
P expression();
P term();
P factor();

bool check(P v){
   return (-10000 <= v.f && v.f <= 10000) && (-10000 <= v.s && v.s <= 10000);
}

P expression(){
   P val = term();
   if(!check(val))return OVERFLOW;
   
   while(s[pos]=='+' || s[pos]=='-'){
      if(s[pos]=='+'){
	 pos++;
	 P tmp = term();
	 if(!check(tmp))return OVERFLOW;
	 val.f += tmp.f;
	 val.s += tmp.s;
	 if(!check(val))return OVERFLOW;
      }
      else{
	 pos++;
	 P tmp = term();
	 if(!check(tmp))return OVERFLOW;
	 val.f -= tmp.f;
	 val.s -= tmp.s;
	 if(!check(val))return OVERFLOW;
      } 
   }
   return val;
}

P term(){
   P val = factor();
   
   if(!check(val))return OVERFLOW;

   while(s[pos]=='*'){
      pos++;
      P tmp1 = val;
      val.f = val.s = 0;
      P tmp2 = factor();
      if(!check(tmp2))return OVERFLOW; 
      val.f += tmp1.f*tmp2.f - tmp1.s*tmp2.s;
      val.s += tmp1.f*tmp2.s + tmp1.s*tmp2.f;
      if(!check(val))return OVERFLOW;
   }
   return val;
}

P factor(){
   P val = mp(0,0);
   
   if(s[pos]=='('){
      pos++;
      val = expression();
      if(!check(val))return OVERFLOW;
      pos++;
   }
   else{
      int tmp = 0;
      while(isdigit(s[pos])){
	 tmp = tmp*10 + (int)(s[pos] - '0');
	 if(tmp < -10000 || 10000 < tmp)return OVERFLOW; 
	 pos++;
      }
      
      if(pos==s.size())val.f = tmp;
      else if(s[pos]=='i'){
 	 val.s = (tmp==0) ? 1 : tmp;
	 pos++;
      }
      else val.f = tmp;
   }
   return val;
}

int main(){
   while(cin >> s){
      pos = 0;
      P ans = expression();
      
      if(ans.f==INF && ans.s==INF)cout << "overflow" << endl;
      else if(ans.f==0 && ans.s==0)cout << "0" << endl;
      else if(ans.f==0)cout << ans.s << "i" << endl;
      else if(ans.s==0)cout << ans.f << endl;
      else cout << ans.f << (ans.s > 0 ? "+" : "") << ans.s << "i" << endl;
   }
   return 0;
}