いろいろがんばりたいブログ

情報科学科の人がいろいろ書きます。

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

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1155

3つの状態を取る変数みっつと、その間の演算がふたつ、および単項演算子がひとつ与えられる。
最終結果が2となるような変数の組を数えるという問題。
もしかしたら、なんかいい感じのほうほうがあるのかもしれないけど、まじめに構文木を作って解いた。

#include <iostream>
#include <map>
#include <string>

using namespace std;

// <formula> ::= 0 | 1 | 2 | P | Q | R |
//               -<formula> | (<formula>*<formula>) | (<formula>+<formula>)

struct Node{
    virtual int eval(map<char,int> vMap)=0;
    Node(){};
};

struct ConstNode : Node{
    int value;
    int eval(map<char,int> vMap){
        return value;
    };
    ConstNode(int val) : value(val) {};
};

struct VarNode : Node{
    char var;
    int eval(map<char,int> vMap){
        return vMap[var];
    }
    VarNode(char va) : var(va) {};
};

struct MinusNode : Node{
    Node* child;
    int eval(map<char,int> vMap){
        int e = (*child).eval(vMap);
        if(e == 0) return 2;
        if(e == 1) return 1;
        if(e == 2) return 0;
    }
    MinusNode(Node* chi) : child(chi) {};
};

struct PlusNode : Node{
    Node *left,*right;
    int eval(map<char,int> vMap){
        int le = (*left).eval(vMap);
        int re = (*right).eval(vMap);
        return max(le,re);
    }
    PlusNode(Node* le,Node* ri) : left(le),right(ri) {};
};

struct MulNode : Node{
    Node *left,*right;
    int eval(map<char,int> vMap){
        int le = (*left).eval(vMap);
        int re = (*right).eval(vMap);
        return min(le,re);
    }
    MulNode(Node *le,Node *ri) : left(le),right(ri) {};
};

struct Result{
    Node *node;
    // next_index
    int index;
    Result(Node *no,int ind) : node(no),index(ind) {};
};


// string,first_index.
Result formula(string,int);
Result mterm(string,int);
Result term(string,int);


Result formula(string s,int ind){
    Result r = mterm(s,ind);
    if(s[r.index] == '+'){
        Result r2 = mterm(s,r.index+1);
        return Result(new PlusNode(r.node,r2.node),r2.index);
    }else if(s[r.index] == '*'){
        Result r2 = mterm(s,r.index+1);
        return Result(new MulNode(r.node,r2.node),r2.index);
    }
    return r;
}

Result mterm(string s,int ind){
    if(s[ind] == '-'){
        Result r = mterm(s,ind+1);
        return Result(new MinusNode(r.node),r.index);
    }else{
        return term(s,ind);
    }
}

Result term(string s,int ind){
    if(s[ind] == '('){
        Result r = formula(s,ind+1);
        // ')'
        r.index++;
        return r;
    }else{
        switch(s[ind]){
        case '0':
        case '1':
        case '2':
            return Result(new ConstNode(s[ind]-'0'),ind+1);
        case 'P':
        case 'Q':
        case 'R':
            return Result(new VarNode(s[ind]),ind+1);
        }
    }
}

int main(){
    while(true){
        string s;
        cin >> s;

        if(s==".") break;
        int cnt = 0;
        Result r = formula(s,0);
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                for(int k=0;k<3;k++){
                    map<char,int> m;
                    m['P'] = i;
                    m['Q'] = j;
                    m['R'] = k;
                    if(r.node->eval(m) == 2){
                        cnt++;
                    }
                }
            }
        }
        cout << cnt << endl;
    }
    return 0;
}