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