ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 2401 Equation

問題文はこちら↓
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2401


・概要
日本語なので省略


・解法
構文解析をするだけです。
ですが、全く構文解析に慣れていなかったので実装するのにすごく時間がかかってしまいました。 ソースコードも無駄な部分が多いと思います。

変数は全部で11個なので全通り(T/F)試せばよいです。


ソースコード

#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<cctype>
using namespace std;

#define REP(i,x,n) for(int i = 0 ; i < (int)(n) ; i++)
#define rep(i,n) REP(i,0,n)

string s;
bool val[11], ans;
int divide, pos1, pos2;

int formula1(){
   int res = 0;
   char c = s[pos1++];
      
   if(c=='a')return val[0];
   if(c=='b')return val[1];
   if(c=='c')return val[2];
   if(c=='d')return val[3];
   if(c=='e')return val[4];
   if(c=='f')return val[5];
   if(c=='g')return val[6];
   if(c=='h')return val[7];
   if(c=='i')return val[8];
   if(c=='j')return val[9];
   if(c=='k')return val[10];
   if(c=='T')return 1;
   if(c=='F')return 0;

   if(c=='-'){
      return 1 - formula1();
   }
   
   if(c=='('){
      int boolA = formula1();
      char op = s[pos1++];
      if(op=='-')pos1++;
      int boolB = formula1();
      pos1++;

      if(op=='-'){
	 if(boolA==1 && boolB==0)return 0;
	 else return 1;
	 }
      if(op=='+'){
	    if(boolA==0 && boolB==0)return 0;
	    else return 1;
      }
      if(op=='*'){
	 if(boolA==1 && boolB==1)return 1;
	 else return 0;
      }
   }
   return -1;
}

int formula2(){
   int res = 0;
   char c = s[pos2++];
      
   if(c=='a')return val[0];
   if(c=='b')return val[1];
   if(c=='c')return val[2];
   if(c=='d')return val[3];
   if(c=='e')return val[4];
   if(c=='f')return val[5];
   if(c=='g')return val[6];
   if(c=='h')return val[7];
   if(c=='i')return val[8];
   if(c=='j')return val[9];
   if(c=='k')return val[10];
   if(c=='T')return 1;
   if(c=='F')return 0;

   if(c=='-'){
      return 1 - formula2();
   }
   
   if(c=='('){
      int boolA = formula2();
      char op = s[pos2++];
      if(op=='-')pos2++;
      int boolB = formula2();
      pos2++;

      if(op=='-'){
	 if(boolA==1 && boolB==0)return 0;
	 else return 1;
	 }
      if(op=='+'){
	    if(boolA==0 && boolB==0)return 0;
	    else return 1;
      }
      if(op=='*'){
	 if(boolA==1 && boolB==1)return 1;
	 else return 0;
      }
   }
   return -1;
}

void solve(int idx){
   if(idx==11){
      if(ans){
	 pos1 = 0;
	 pos2 = divide;
	 
	 if(formula1()!=formula2()){
	    ans = false;
	    return ;
	 }
      }
   }
   
   else{
      val[idx] = true;
      solve(idx+1);
      val[idx] = false;
      solve(idx+1);
   }
}

int main(){
   while(cin >> s){
      if(s=="#")break;
     
      rep(i,s.size()){
	 if(s[i]=='='){
	    divide = i+1;
	    break;
	 }
      }
      ans = true;
      solve(0);
      cout << (ans ? "YES" : "NO") << endl;
   }
   return 0;
}