UVa11954 Binary Calculator

問題文
http://uva.onlinejudge.org/external/119/11954.html

解法１
二項演算子に遭遇するたびに両側区間で再帰する。（普通の構文解析と同じ）1000文字までのビットが存在しうるので、数字は deque で各桁の値(1 or 0)を管理する。

単項演算子の優先順位は数値に近いものから処理する。また、二項演算子は左から処理する。

また、単項演算子を適用する前に leading0 を全て削除する必要がある。でないと not を使うときにバグってしまう。

解法２
whileループで解く（自分は未実装）。
初めは単項演算子とビット列の区別をセずにビット列と二項演算子のみの問題と考えて実装する。
実装が間違っていないことをデバッグによって確認できたら、ビット列の読み込みの部分を単項演算子も認識するように拡張する。

こうやって段階を踏むと解ける（はず）。

反省
自分のコードでは、左から計算するために二項演算子を右から見つける必要があった。それに気づかずWAを量産してしまった。
また初めに、処理しやすいように入力の演算子を全て一文字に変換して、空白を全て排除してつなげた。

全てのコードを書く前に、再帰の際に区間の内容が正しいか表示するデバッグを挟むと、こういう問題のミスが減少するかもしれない。危なそうなところは全てデバッグを挟んで逐次結果を確かめると良い。二度同じデバッグのコードを書かないよう、プリプロセッサの活用が効果的。

#include <bits/stdc++.h>
 
using namespace std;
 
typedef deque<int> BigInt;
 
BigInt toNum10(const string &s) {
  int const N = s.size();
  BigInt ret;
  for(int i=0; i<N; i++) {
    if(s[i]-'0') { ret.push_back(1); }
  }
  return ret;
}
 
BigInt trimleftzero(const BigInt &x) {
  BigInt ret;
  bool zerof = false;
  for(int i=0; i<(int)x.size(); i++) {
    if(x[i] != 0) zerof = true;
    if(zerof) {
      ret.push_back(x[i]);
    }
  }
  if(ret.size()==0) ret.push_back(0);
  return ret;
}
 
string toStr2(const BigInt &x) {
  string ret;
  BigInt b = trimleftzero(x);
  for(int i=0; i<(int)b.size(); i++) {
    ret.push_back(b[i]+'0');
  }
  return ret;
}
 
BigInt bop(const BigInt &a, char op, const BigInt &b) {
   
  int N = max(a.size(), b.size());
  BigInt ret, A = a, B = b;
   
  for(int i=a.size(); i<N; i++) A.push_front(0);
  for(int i=b.size(); i<N; i++) B.push_front(0);
   
  for(int i=0; i<N; i++) {
    if(op=='^') ret.push_back(A[i]^B[i]);
    if(op=='&') ret.push_back(A[i]&B[i]);
    if(op=='|') ret.push_back(A[i]|B[i]);
  }
   
  return ret;
}
 
string line;
BigInt rec(int l, int r) {
#ifdef DEBUG
  cout << line.substr(l, r-l) << endl;
#endif
  // binary operator
  for(int i=r-1; i>=l; i--) {
    switch(line[i]) {
    case '^': case '&': case '|':
      return bop(rec(l, i), line[i], rec(i+1, r));
    }
  }
   
  // unary operator
  deque<char> unaries;
  BigInt t;
   
  for(int i=l; i<r; i++) {
    switch(line[i]) {
    case '~': case '<': case '>':
      unaries.push_front(line[i]);
      break;
    default:
      for(; i<r && isdigit(line[i]); i++) {
        t.push_back(line[i]-'0');
      }
      i--;
      for(unsigned j=0; j<unaries.size(); j++) {
        t = trimleftzero(t);
        switch(unaries[j]) {
        case '~':
          for(int k=0; k<(int)t.size(); k++) t[k] = 1 - t[k];
          break;
        case '<':
          t.push_back(0);
          break;
        case '>':
          t.pop_back();
          break;
        }
      } // for j
      unaries.clear();
      goto EXIT;
    }
  }
   
 EXIT:
  return t;
}
 
int main() {
   
  int Tc; cin >> Tc; cin.ignore();
  for(int Tcnt=1; Tcnt<=Tc; Tcnt++) {
    string s, t; getline(cin, s);
    stringstream ss(s);
    line.clear();
    while(ss >> t) {
      if(t=="not") t = "~";
      if(t=="shl") t = "<";
      if(t=="shr") t = ">";
      if(t=="xor") t = "^";
      if(t=="and") t = "&";
      if(t=="or")  t = "|";
      line += t;
    }
    cout << "Case " << Tcnt << ": "
         << toStr2(rec(0, line.size())) << endl;
  }
   
  return 0;
}