PKU 1100 Dreisam Equations

http://poj.org/problem?id=1100
与えられた等式を満たすような演算子を必要なところに当てはめるというような問題。
ただし、基本的に演算の順序は前から行うようです。

入力がなかなか鬼畜なようで、データセットを見てしまいまいた。
コンパイラとかの構文解析って大変そうですね。
BNFは以下のような感じになるんじゃないでしょうか。

expr := fact | expr+fact | expr-fact | expr*fact
fact := (expr) | number

int stoi(const string&in){
  stringstream ss(in);
  int ret;
  ss>>ret;
  return ret;
}

string in;
int apos;
int ri;

int expr();

int getnum(){
  int ret=0;
  while(apos<SZ(in) && isdigit(in[apos]))ret=ret*10+in[apos++]-'0';
  return ret;
}

int fact(){
  int ret;
  if(in[apos]=='('){
    ++apos;
    ret=expr();
    ++apos;
  }else ret=getnum();
  return ret;
}


int expr(){
  int ret=fact();
  while(apos<SZ(in) && in[apos]!=')'){
    char op=in[apos++];
    int b=fact();
    if(op=='+')ret+=b;
    else if(op=='*')ret*=b;
    else ret-=b;
  }
  return ret;
}
int pr=0;
bool dfs(int pos){
  while(pos<SZ(in) && in[pos]!=' ')++pos;
  if(pos==SZ(in)){
    apos=0;
    int res=expr();
    return ri==res;
  }

  char op[]={'+','-','*'};
  rep(i,3){
    in[pos]=op[i];
    if(dfs(pos+1))return true;
    in[pos]=' ';
  }
  return false;
}

main(){
  string so;
  int eq=0;
  while(getline(cin,so)){
    if(so[0]=='0')break;
    int sp=0;
    string temp=so;
    so.clear();
    rep(i,SZ(temp)){
      if(temp[i]==' ')continue;
      if(temp[i]=='(' && (SZ(so)==0 || so[SZ(so)-1]!='('))so+=" (";
      else if(isdigit(temp[i]) && SZ(so) && so[SZ(so)-1]==')')so+=' ',so+=temp[i];
      else if(isdigit(temp[i]) && i && temp[i-1]==' ' && SZ(so) &&
              (isdigit(so[SZ(so)-1]) || so[SZ(so)-1]==')'))so+=' ',so+=temp[i];
      else so+=temp[i];
    }


    ++eq;
    cout<<"Equation #"<<eq<<':'<<endl;
    
    in=so.substr(so.find('=')+1);
    if(in[0]==' ')in=in.substr(1);

    ri=stoi(so.substr(0,so.find('=')));
    if(dfs(0))cout<<ri<<'='<<in<<endl;
    else cout<<"Impossible"<<endl;
    cout<<endl;
  }
}