せっかく構文解析の練習を少ししたので
問題概要
-(a+b)=(-a*-b) (a->b)=(-a+b) ((a*T)+b)=(-c+(a*-b))
のような式たちが恒等式かどうかを判定せよ。すなわち、a や b や c に true と false をどのように当てはめても結果が一致するかどうかを判定せよ。
解法
BNF が
<equation> ::= <formula> "=" <formula> <formula> ::= "T" | "F" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "-" <formula> | "(" <formula> "*" <formula> ")" | "(" <formula> "+" <formula> ")" | "(" <formula> "->" <formula> ")"
のように与えられているので、この通りに構文解析すればよい。実際の判定は bit 全探索で行う。
#include <iostream> #include <vector> #include <string> #include <sstream> using namespace std; template<class T> struct Parser { // results int root; // vals[root] is the answer vector<T> vals; // value of each node vector<string> ops; // operator of each node ('a' means leaf values) vector<int> left, right; // the index of left-node, right-node vector<int> ids; // the node-index of i-th value int id = 0; void init() { vals.clear(); ops.clear(); left.clear(); right.clear(); ids.clear(); id = 0; } // generate nodes int newnode(string op, int lp, int rp, T val = 0) { ops.push_back(op); left.push_back(lp); right.push_back(rp); if (op == "x") vals.push_back(val), ids.push_back(id++); else { if (op == "a") vals.push_back(val); else if (op == "-") vals.push_back(!vals[lp]); else if (op == "+") vals.push_back(vals[lp] || vals[rp]); else if (op == "*") vals.push_back(vals[lp] && vals[rp]); else if (op == "->") vals.push_back(!vals[lp] || vals[rp]); ids.push_back(-1); } return (int)vals.size() - 1; } // main solver T solve(const string &S) { init(); int p = 0; root = formula(S, p); return vals[root]; } // parser int formula(const string &S, int &p) { if (S[p] == '-') { ++p; int lp = formula(S, p); return newnode("-", lp, -1); } else if (S[p] == '(') { ++p; int lp = formula(S, p); string op = ""; if (S[p] == '+') ++p, op = "+"; else if (S[p] == '*') ++p, op = "*"; else if (S[p] == '-') p += 2, op = "->"; int rp = formula(S, p); ++p; // skip ')' return newnode(op, lp, rp); } else if (S[p] == 'T') { ++p; return newnode("a", -1, -1, true); } else if (S[p] == 'F') { ++p; return newnode("a", -1, -1, false); } else { ++p; return newnode("x", -1, -1); } } }; int main() { string S; Parser<bool> p1, p2; while (cin >> S) { if (S == "#") break; for (int i = 0; i < S.size(); ++i) if (S[i] == '=') S[i] = ' '; bool res = true; for (int bit = 0; bit < (1<<11); ++bit) { string SS = S; for (int i = 0; i < SS.size(); ++i) { if (SS[i] >= 'a' && SS[i] <= 'k') { int id = SS[i] - 'a'; if (bit & (1<<id)) SS[i] = 'T'; else SS[i] = 'F'; } } istringstream si(SS); string s1, s2; si >> s1 >> s2; bool r1 = p1.solve(s1), r2 = p2.solve(s2); if (r1 != r2) res = false; } if (res) cout << "YES" << endl; else cout << "NO" << endl; } }