AOJ 1155 Problem C: 如何に汝を満足せしめむ? いざ数え上げむ…
題名長いっすね。構文解析の練習です。だいぶ慣れてきた。
解法
formulaにしたがって構文解析する。
typedef string::const_iterator State; int formula(State& begin, int s); int factor(State& begin, int s); void consume(State& begin, char expected) { if (*begin == expected) begin++; else { cout << "expected: " << expected << endl; cout << "but *begin is " << *begin << endl; cout << "rest string is" << endl; while (*begin) { cout << *begin++ ; } cout << endl; exit(1); } } int formula(State& begin, int s) { if (*begin == '-') { consume(begin, '-'); return 2-formula(begin, s); } else if (*begin == '(') { consume(begin, '('); int ret = formula(begin, s); if (*begin == '*') { consume(begin, '*'); ret = min(ret, formula(begin, s)); } else if (*begin == '+') { consume(begin, '+'); ret = max(ret, formula(begin, s)); } consume(begin, ')'); return ret; } else { return factor(begin, s); } } int factor(State& begin, int s) { int ret = 0; if (isdigit(*begin)) ret = *begin - '0'; else { if (*begin == 'P') ret = ((s%3)); else if (*begin == 'Q') ret = ((s/3)%3); else ret = ((s/9)); } begin++; return ret; } void solve(const string& s) { int ans = 0; for (int S = 0; S < 27; S++) { State begin = s.begin(); if (formula(begin, S) == 2) ans++; } cout << ans << endl; } int main() { cin.tie(0); ios::sync_with_stdio(false); string s; while (cin >> s) { if (s == ".") break; solve(s); } return 0; }