UVa 11954 Binary Calculator

http://uva.onlinejudge.org/contests/279-c0158285/11954.html
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=229&page=show_problem&problem=3105 (現在問題が見えなていないので上のリンクを見てください)

昨日の復習。構文解析する問題。

与えられた構文ルールが微妙なせいで、逆に分かりにくくなっている気がします。素直にやろうとしたら優先順位とかで死にまくっていたようです。コンテスト中に解きたかったなと思いました。

string in;
int pos;

string number(){
  string ret;
  while(pos<SZ(in) && isdigit(in[pos]))ret+=in[pos++];
  while(SZ(ret)>1 && ret[0]=='0')ret=ret.substr(1);
  return ret;
}


string token(){
  string ret;
  if(isdigit(in[pos]))return number();

  string op=in.substr(pos,3);
  pos+=3;
  ret=token();
  if(op=="not"){
    rep(i,SZ(ret)){
      if(ret[i]=='0')ret[i]='1';
      else ret[i]='0';
    }
  }else if(op=="shr"){
    if(SZ(ret)>1)ret=ret.substr(0,SZ(ret)-1);
    else ret="0";
  }else{
    ret+='0';
    while(SZ(ret)>1 && ret[0]=='0')ret=ret.substr(1);
  }

  while(SZ(ret)>1 && ret[0]=='0')ret=ret.substr(1);
  return ret;
}

string expression(){
  string ret=token();
  string li;
  while(pos<in.size()){
    li=ret;
    ret="";
    string op;
    if(in[pos]!='o'){
      op=in.substr(pos,3);
      pos+=3;
    }else{
      op=in.substr(pos,2);
      pos+=2;
    }
    string ri=token();
    int sz=max(SZ(li),SZ(ri));
    while(SZ(ri)<sz)ri='0'+ri;
    while(SZ(li)<sz)li='0'+li;
    if(op=="or"){
      rep(i,SZ(li)){
        if(li[i]=='1' || ri[i]=='1')ret+='1';
        else ret+='0';
      }
    }else if(op=="and"){
      rep(i,SZ(li)){
        if(li[i]=='1' && ri[i]=='1')ret+='1';
        else ret+='0';
      }
    }else{
      rep(i,SZ(li)){
        if(li[i]+ri[i]-2*'0'==1)ret+='1';
        else ret+='0';
      }
    }
  }
  while(SZ(ret)>1 && ret[0]=='0')ret=ret.substr(1);
  return ret;
}

main(){
  int test;
  cin>>test;
  cin.ignore();
  rep(ca,test){
    cout<<"Case "<<ca+1<<": ";
    string temp;
    getline(cin,temp);
    in="";
    pos=0;
    rep(i,SZ(temp))if(temp[i]!=' ')in+=temp[i];
    string ans=expression();
    cout<<ans<<endl;
  }
}