mayoko’s diary

プロコンとかいろいろ。

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