中置表現の評価（括弧付き）

中置表現を直接評価するには、演算子の優先順位と括弧の処理を正しく扱う必要がある。以下の実装では、2つのスタック（数値用と演算子用）を用いて、入力文字列を1パスで処理する。

#include <bits/stdc++.h>
using namespace std;

stack<int> nums;
stack<char> ops;
unordered_map<char, int> precedence = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};

void calculate() {
    int right = nums.top(); nums.pop();
    int left = nums.top(); nums.pop();
    char op = ops.top(); ops.pop();

    switch (op) {
        case '+': nums.push(left + right); break;
        case '-': nums.push(left - right); break;
        case '*': nums.push(left * right); break;
        case '/': nums.push(left / right); break;
    }
}

int main() {
    string expr;
    cin >> expr;

    for (int i = 0; i < expr.size(); ++i) {
        char ch = expr[i];

        if (isdigit(ch)) {
            int value = 0;
            while (i < expr.size() && isdigit(expr[i])) {
                value = value * 10 + (expr[i++] - '0');
            }
            --i;
            nums.push(value);
        } else if (ch == '(') {
            ops.push(ch);
        } else if (ch == ')') {
            while (ops.top() != '(') calculate();
            ops.pop(); // '(' を削除
        } else {
            while (!ops.empty() && ops.top() != '(' &&
                   precedence[ops.top()] >= precedence[ch]) {
                calculate();
            }
            ops.push(ch);
        }
    }

    while (!ops.empty()) calculate();
    cout << nums.top() << endl;
    return 0;
}

後置表現（逆ポーランド記法）の評価

後置表現では括弧が不要で、左から右に単純に処理できるため、実装が容易である。数字はスタックに積み、演算子が現れたら直近の2つの値を取り出して計算し、結果を再びスタックに格納する。

#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int> stk;
    string token;
    
    while (cin >> token) {
        if (token == "@") break;

        if (token.back() == '.') {
            // 数字トークン（末尾に '.'）
            int num = stoi(token.substr(0, token.size() - 1));
            stk.push(num);
        } else {
            // 演算子
            int b = stk.top(); stk.pop();
            int a = stk.top(); stk.pop();
            int result;

            switch (token[0]) {
                case '+': result = a + b; break;
                case '-': result = a - b; break;
                case '*': result = a * b; break;
                case '/': result = a / b; break;
                default: result = 0;
            }
            stk.push(result);
        }
    }

    cout << stk.top() << endl;
    return 0;
}