NYOJ 128 前綴表達式求值 - 棧計算

問題描述

輸入前綴表達式（操作符與操作數以空格分隔），如 + 2 * + 3 4 5，求值並保留兩位小數。操作數可能為小數，操作符 + - * /。

解法：從右向左掃描 + 棧

前綴表達式從右向左掃描最自然：遇到數字入棧；遇到操作符彈出兩個數計算（先彈出為左操作數，後彈出為右操作數），結果入棧。最終棧頂為答案。

代碼實現（C++）

#include 
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string line;
    while (getline(cin, line)) {
        if (line.empty()) continue;
        stringstream ss(line);
        vector tokens;
        string tok;
        while (ss >> tok) tokens.push_back(tok);
        stack st;
        for (int i = tokens.size() - 1; i >= 0; i--) {
            string t = tokens[i];
            if (t == "+" || t == "-" || t == "*" || t == "/") {
                double a = st.top(); st.pop();
                double b = st.top(); st.pop();
                double res = 0;
                if (t == "+") res = a + b;
                else if (t == "-") res = a - b;
                else if (t == "*") res = a * b;
                else if (t == "/") res = a / b;
                st.push(res);
            } else {
                st.push(stod(t));
            }
        }
        cout << fixed << setprecision(2) << st.top() << '\n';
    }
    return 0;
}

關鍵點

• 從右向左掃描避免複雜的操作符優先級處理。
• 操作數順序：先彈出 a（左），後彈出 b（右），計算 a op b。
• 用 stringstream 分割 token，支持小數。
• 輸出 fixed + setprecision(2)。