AOJ 2401: Equation

問題リンク : Equation | Aizu Online Judge

問題概要 :
与えられた等式が恒等式であるかどうかを判定しろ

使用した言語: C++

解法 :
与えられた真理値表の通り構文解析する。変数は１１個しかないので全部試しても2の11乗(2048)しかないのでまさかの十一重ループを書いてみたりした。

コード :

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stdexcept>
#include<cmath>
#include<memory>
#include<algorithm>
#include<cstring>
#include<ctime>
#include<deque>
#include<sstream>
#include<iomanip>
#include<sstream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<climits>
#include<map>
#include<set>
#include<list>
#include<cassert>
#include<deque>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define INF 1<<27
#define all(n) n.begin(),n.end()
#define insert(a,b,c,d) PP(P(a,b),P(c,d))
#define F first
#define S second
#define pb push_back
#define pf push_front
#define LIM 100000
using namespace std;
typedef pair<int,int> P;
typedef pair<P,P> PP;
typedef long long ll;
typedef unsigned long long ull;
 
 
class Parsing{
private:
  string parse;
  int pos;
  map<char,bool> val;
public:
 
  Parsing(string s,bool a,bool b,bool c,bool d,bool e,bool f,bool g,bool h,bool i,bool j,bool k){
    parse = s;
    pos = 0;
    val['a'] = a,val['b'] = b,val['c'] = c,val['d'] = d,val['e'] = e,val['f'] = f,val['g'] = g,val['h'] = h,val['i'] = i,val['j'] = j,val['k'] = k;
  }
 
  bool fact(){
    if(parse[pos] == '('){
      pos++;
      bool p = expression();
      pos++;
      return p;
    }else if(parse[pos] == '-'){
      pos++;
      bool p = fact();
     
      return p?false:true;
    }else{
      if('a' <= parse[pos] && parse[pos] <= 'k'){
    pos++;
    return val[parse[pos-1]];
      }      
      else if(parse[pos] == 'T' || parse[pos] == 'F'){
    ++pos;
    return parse[pos-1] == 'T'?1:0;
      }
      assert(false);
    }
  }
   
  bool term(){
    bool p = fact();
    
    return p;
  }
   
  bool expression(){
 
    bool p = term();
    
    while(parse[pos] == '+' || parse[pos] == '*' || parse.substr(pos,2) == "->" ){
      if(parse[pos] == '+'){
    pos++;
    bool q = term();
    p = p|q;
      }
      else if(parse[pos] == '*'){
    pos++;
    bool q = term();
    p = p&q;
      }
      else if(parse.substr(pos,2) == "->"){
    pos+=2;
    bool q = term();
    if(p && !q)p = false;
    else p = true;
        }
    }
    return p;
  } 
};
 
int main(){
 
  while(true){
    string s1,s2,s;
    cin >> s;
    if(s[0] == '#')break;
    for(int i=0;i<s.length();i++){
      if(s[i] == '='){
    s1 = s.substr(0,i);
    s2 = s.substr(i+1,s.length()-i-1);
    break;
      }
    }
    
    bool yes = true;
    rep(a,2){    
      rep(b,2){
    rep(c,2){
      rep(d,2){
        rep(e,2){
          rep(f,2){
        rep(g,2){
          rep(h,2){
            rep(i,2){
              rep(j,2){
            rep(k,2){
              Parsing par1(s1,a,b,c,d,e,f,g,h,i,j,k);
              Parsing par2(s2,a,b,c,d,e,f,g,h,i,j,k);
              if(par1.expression() != par2.expression() ){
                yes = false;
                break;
              }
            }
            if(!yes)break;
              }
              if(!yes)break;
            }
            if(!yes)break;
          }
          if(!yes)break;
        }
        if(!yes)break;
          }
          if(!yes)break;
        }
        if(!yes)break;
      }
      if(!yes)break;
    }
    if(!yes)break;
      }
      if(!yes)break;
    }
    yes?cout << "YES" << endl:cout << "NO" << endl;
  }
return 0;
}