こういうのをサッと書けるようになりたいね

問題概要

((6 + 2) + 1) + (7 * 6) + 3

のような計算式が以下のような入力フォーマットで与えられる。これを構文解析して計算結果を出力せよ。

演算子は「+」「*」のみ
数値は 1 桁のみ

10
+
.+
..6
..2
.+
..1
..*
...7
...6
.3

解法

色々ありそう。再帰つかったりとかも。僕は stack を使ってみた。現在の演算状態を

{3, +, 5, ×, 4 +, 2 +, ...}

のような感じで管理してみることにした。ただし、「+」は -1、「×」は -2 とした。

..+
...5

みたいなやつは、その前のやつの最後尾が {..., 100, +} とかだったとすると、

{..., 100, +}
↓
{..., 105, +}

という風になる。また、

「+」が来た瞬間には、{0, +} を push する
「*」が来た瞬間には、{1, ×} を push する

という風にしている。さらに

.....5
...3

みたいなやつは現実の計算では、「)) +」「)) ×」みたいな感じにカッコ閉じに対応している。これは stack の最後尾から順に前へ前へと計算を伝播して行けばいい。ちょうど逆ポーランド法に近い感じの要領で。

上の例だとこんな感じに遷移する。

0, +
0, +, 0, +
0, +, 6, +
0, +, 8, +
8, +, 0, + (1 回計算結果を {8, +} と畳んでから再び「+」に対応するものを push)
8, +, 1, +
8, +, 1, +, 1, × (「×」に対応する {1, ×} を push)
8, +, 1, +, 7, ×
8, +, 1, +, 42, ×
54, +

以上を実装するとこんな感じになった。

#include <iostream>
#include <string>
#include <stack>
using namespace std;

void Push(stack<long long> &st, long long val) {
    int op = st.top(); st.pop();
    long long back = st.top(); st.pop();
    if (op == -1) back += val;
    else back *= val;
    st.push(back);
    st.push(op);
}

void Pop(stack<long long> &st) {
    st.pop();
    long long val = st.top(); st.pop();
    int op = st.top(); st.pop();
    long long back = st.top(); st.pop();
    if (op == -1) back += val;
    else back *= val;
    st.push(back);
    st.push(op);
}

int main() {
    int n;
    while (cin >> n) {
        if (n == 0) break;
        if (n == 1) {
            int num; cin >> num;
            cout << num << endl;
        }
        else {
            stack<long long> st;
            for (int _ = 0; _ < n; ++_) {
                string str; cin >> str;
                int s = (int)str.size() - 1;

                while (st.size() > s * 2) Pop(st);
                if (str.back() == '+') st.push(0), st.push(-1);
                else if (str.back() == '*') st.push(1), st.push(-2);
                else Push(st, str.back() - '0');
            }
            while (st.size() > 2) Pop(st);
            st.pop();
            cout << st.top() << endl;
        }
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 1602 ICPC 計算機 (ICPC 国内予選 2015 C) (250 点)

問題概要

解法