AOJ 1155: How can I satisfy thee? Let me count the ways...

問題

How can I satisfy thee? Let me count the ways... | Aizu Online Judge

"true", "false", "unknown"の3種類があるロジックで、与えられた式を満たすP, Q, Rの組み合わせが何種類あるか数えよ

方針

  • P, Q, Rがそれぞれ3通りの値を取るため27通りしかないから全てを評価して満たす場合を数えればよい
  • 再帰下降構文解析をすればよい

コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)

int formula(string &s, int P, int Q, int R, int &i) {
    if(s[i] == '-') {
        i++;
        return 2-formula(s, P, Q, R, i);
    } else if(s[i] == '(') {
        int X, Y;
        i++;
        X = formula(s, P, Q, R, i);
        if(s[i] == '*') {
            i++;
            Y = formula(s, P, Q, R, i);
            i++;
            if(X == 0) return 0;
            if(X == 1) {
                if(Y == 0) return 0;
                else return 1;
            } else {
                return Y;
            }
        } else {
            i++;
            Y = formula(s, P, Q, R, i);
            i++;
            if(X == 0) return Y;
            if(X == 1) {
                if(Y == 0) return 1;
                else return Y;
            } else {
                return 2;
            }
        }
    } else {
        int ret;
        if(s[i] >= '0' && s[i] <= '2') ret = s[i]-'0';
        else if(s[i] == 'P') ret = P;
        else if(s[i] == 'Q') ret = Q;
        else if(s[i] == 'R') ret = R;
        i++;
        return ret;
    }
}

int main(void){
    string s;
    while(cin >> s && s != ".") {
        int cnt = 0;
        rep(i, 3) rep(j, 3) {
            rep(k, 3) {
                int index = 0;
                if(formula(s, i, j, k, index) == 2) cnt++;
            }
        }
        cout << cnt << endl;
    }
}

反省

  • LL(1)文法のパーサーは初めてだったので手間取った