PKU 1779 Boolean Logic

http://poj.org/problem?id=1779
結構がっつりしている気がする構文解析。
演算ごとにその結果を覚えておく必要がある。

まず入力と出力の形式が面倒くさい。
等と思ってしまいながら実装しました。
こういう構文解析を書く時はたまに、コンパイラとかの実装ではどうやって空白の処理をしているのか気になります。<->の演算子で!=と==を間違えてサンプルがあってないのに出して1WA。

変数rはいらなかったよう気がします。

string in;
vector<int> po;
int c2i[128];
vector<char> app;
string out;

bool op(int idx){
  return !isalpha(in[idx]) && in[idx]!=')' && in[idx]!='(';
}

bool expr(int l,int r){
  if(isalpha(in[l]))
    return out[po[l]]=c2i[in[l]];

  if(in[l+1]=='!')return out[po[l+1]]=!expr(l+2,r-1);

  int rp=0;
  for(int me=l;me<r;++me){
    if(in[me]=='(')--rp;
    if(in[me]==')')++rp;
    if(rp==-1 && op(me)){
      int a=expr(l+1,me);
      int b;
      if(in[me]=='&' || in[me]=='|')b=expr(me+1,r-1);
      else b=expr(me+3,r-1);
      switch(in[me]){
      case '&':
        return out[po[me]]=a&b;
      case '|':
        return out[po[me]]=a|b;
      case '-':
        return out[po[me+1]]=a<=b;
      case '<':
        return out[po[me+1]]=a==b;
      }
    }
  }
}

void dfs(int ne){
  if(ne==SZ(app)){
    expr(0,SZ(in));
    FOR(it,out)if(*it!=' ')*it+='0';
    cout<<out<<endl;
    return;
  }
  rep(i,2){
    c2i[app[ne]]=i;
    dfs(ne+1);
  }
}

main(){
  string sin;
  while(getline(cin,sin)){
    in.clear();
    po.clear();
    app.clear();
    memset(c2i,0,sizeof(c2i));
    rep(i,SZ(sin)){
      if(sin[i]!=' '){
        in+=sin[i];
        po.pb(i);
        c2i[sin[i]]=1;
        if(isalpha(sin[i]))app.pb(sin[i]);
      }
    }
    sort(ALL(app));
    app.erase(unique(ALL(app)),app.end());
    cout<<sin<<endl;
    out=string(SZ(sin),' ');
    dfs(0);
    cout<<endl;
  }
}