けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 2401 恒等式

せっかく構文解析の練習を少ししたので

問題へのリンク

問題概要

-(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;
    }
}