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);
  }
}