AOJ2401 恒等式

問題概要

---

与えられた等式が，すべての場合において成り立つかどうか判定する。
定数: T, F
変数: a, b, c, d, e, f, g, h, i, j, k
論理否定: -X
論理積: (X*Y)
論理和: (X+Y)
論理包含: (X->Y)

解法

---

構文解析する。変数が最大11個なのですべての場合において試した。

ソース

---

#include<iostream>
#include<string>
#include<map>
#include<sstream>
#include<cctype>
#include<algorithm>
using namespace std;
typedef string::const_iterator Cursol;
bool ok;
int bit;
bool Formula(Cursol &c){
  bool ret;
  if(*c == 'T') ret = true;
  else if(*c == 'F') ret = false;
  else if(islower(*c)) ret = bit >> ((*c) - 'a') & 1;
  else if(*c == '-') return !Formula(++c);
  else if(*c == '('){
    ret = Formula(++c);
    if(*c == '+'){
      ret |= Formula(++c);
    }else if(*c == '*'){
      ret &= Formula(++c);
    }else if(*c == '-'){ //->
      c++;
      ret = !ret | Formula(++c);
    }
  }
  c++;
  return ret;
}
int main(){
  string s;
  Cursol c;
  while(cin >> s , ok = true, s != "#"){
    string l = s.substr(0,s.find('='));
    string r = s.substr(s.find('=')+1);

    for(bit = 0 ; bit < (1 << 11) ; bit++ ){
      c = l.begin();
      bool java = Formula(c);
      c = r.begin();
      if( java != Formula(c) ){
 ok = false;
 break;
      }
    }
    if(ok) cout << "YES" << endl;
    else cout << "NO" << endl;
  }
}