AOJ 109 Smart Calculator - mayoko’s diary

今日残りの国内予選の幾何問題を見てて察したのですが,幾何問題は面倒すぎて多分「普通だったら特に練習しなくても解けるし難しかったら解けない」という気がするので構文解析の技術を身につけるほうが良さそうな気がしてきました。ということではい。

問題

解法

このページに非常に丁寧に説明があるのでこれを参考にしました。
構文解析 Howto

僕はC++弱者なのでconst_iteratorってなんのことやらよくわかりませんでしたがこのページをみてなんとなく理解しました。
const_iterator - ルギア君の戯言

問題文に書いてある制約だけだとlong longを超える整数が登場してもおかしくないんですがintであっさりでした。そこらへんはちゃんと書いて欲しいよね(よく読んでないだけ？)。

typedef string::const_iterator State;

int expression(State& begin);
int term(State& begin);
int number(State& begin);
int factor(State& begin);

int expression(State& begin) {
    int ret = term(begin);
    for (;;) {
        if (*begin == '+') {
            begin++;
            ret += term(begin);
        } else if (*begin == '-') {
            begin++;
            ret -= term(begin);
        } else break;
    }
    return ret;
}

int term(State& begin) {
    int ret = factor(begin);
    for (;;) {
        if (*begin == '*') {
            begin++;
            ret *= factor(begin);
        } else if (*begin == '/') {
            begin++;
            ret /= factor(begin);
        } else break;
    }
    return ret;
}

int factor(State& begin) {
    if (*begin == '(') {
        begin++;
        int ret = expression(begin);
        begin++;
        return ret;
    } else {
        return number(begin);
    }
}

int number(State& begin) {
    int ret = 0;
    while (isdigit(*begin)) {
        ret = ret*10 + (*begin - '0');
        begin++;
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    cin.ignore();
    for (int i = 0; i < n; i++) {
        string s;
        getline(cin, s);

        State begin = s.begin();
        int ans = expression(begin);
        cout << ans << endl;
    }
    return 0;
}