AOJ 2401 恒等式

デバッグに非常に時間がかかったけどなんとか出来た。

問題

Equation | Aizu Online Judge

解法

問題文中に最高のヒントが書いてあるのでそれを元に関数を作る。

<equation> ::= <formula> "=" <formula>
<formula>  ::= "T" | "F" |
"a" | "b" | "c" | "d" | "e" | "f" |
"g" | "h" | "i" | "j" | "k" |
"-" <formula> |
"(" <formula> "*" <formula> ")" |
"(" <formula> "+" <formula> ")" |
"(" <formula> "->" <formula> ")"

最後まで残ったバグは"a->b"のときaがtrueでbがfalseならfalseなのは良いんですがそれ以外の場合にaをtrueにする処理を書き忘れていました。
まぁデバッグの手法も学べた(consume関数)ので良し。

typedef string::const_iterator State;

bool formula(State& begin, int S);
bool TF(State& begin, int S);

void consume(State& begin, char expected) {
    if (*begin == expected) {
        begin++;
    } else {
        cerr << "Expected '" << expected << "' but got '" << *begin << "'" << endl;
        cerr << "Rest string is '";
        while (*begin) {
            cerr << *begin++;
        }
        cerr << "'" << endl;
        exit(1);
    }
}

bool formula(State& begin, int S) {
    if (*begin == '-') {
        begin++;
        return !formula(begin, S);
    } else if (*begin == '(') {
        consume(begin, '(');
        bool ret = formula(begin, S);
        if (*begin == '*') {
            consume(begin, '*');
            ret &= formula(begin, S);
            consume(begin, ')');
            return ret;
        } else if (*begin == '+') {
            consume(begin, '+');
            ret |= formula(begin, S);
            consume(begin, ')');
            return ret;
        } else {
            consume(begin, '-');
            consume(begin, '>');
            bool tmp = formula(begin, S);
            if (ret == true && tmp == false) ret = false;
            else ret = true;
            consume(begin, ')');
            return ret;
        }
    } else {
        return TF(begin, S);
    }
}

bool TF(State& begin, int S) {
    if (*begin == 'T') {
        consume(begin, 'T');
        return true;
    }
    if (*begin == 'F') {
        consume(begin, 'F');
        return false;
    }
    int tmp = *begin - 'a';
    begin++;
    return ((S>>tmp)&1) == 1;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (1) {
        bool ng = false;
        string s;
        cin >> s;
        if (s == "#") break;
        for (int i = 0; i < 2048; i++) {
            State begin1 = s.begin(), begin2;
            for (begin2 = s.begin(); ; begin2++) {
                if (*begin2 == '=') {
                    begin2++;
                    break;
                }
            }
            if (formula(begin1, i) != formula(begin2, i)) {
                ng = true;
                break;
            }
        }
        if (ng) {
            cout << "NO" << endl;
        } else {
            cout << "YES" << endl;
        }
    }
    return 0;
}