HDOJ 1237 簡單計算器：堆疊實現四則運算表達式求值

問題描述

讀取只包含 +, -, *, / 的非負整數算術表達式（整數與運算符以空格分隔），計算其值，結果保留小數點後兩位。輸入以單獨一行 "0" 結束。

堆疊解法

利用一個堆疊儲存已處理的項。掃描表達式：

• 讀入第一個數，壓入堆疊。
• 之後每次讀運算符 op 和數字 num：
  • op == '+'：壓入 +num。
  • op == '-'：壓入 -num。
  • op == '*'：彈出棧頂 x，壓入 x * num。
  • op == '/'：彈出棧頂 x，壓入 x / num。
• 最後將堆疊中所有數相加即為結果。

此法利用乘除優先級高於加減，直接在棧頂完成乘除運算，將表達式轉化為純加法求和。

複雜度

• 時間：O(L)，L 為表達式長度。
• 空間：O(L) 最壞情況。

參考程式碼 (C++)

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

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    double num;
    while (cin >> num) {
        if (num == 0 && cin.peek() == '\n') break; // 單獨一行 0
        stack st;
        st.push(num);
        char op;
        while (cin >> op >> num) {
            if (op == '+') st.push(num);
            else if (op == '-') st.push(-num);
            else if (op == '*') { double x = st.top(); st.pop(); st.push(x * num); }
            else if (op == '/') { double x = st.top(); st.pop(); st.push(x / num); }
            if (cin.peek() == '\n') break;
        }
        double sum = 0;
        while (!st.empty()) { sum += st.top(); st.pop(); }
        cout << fixed << setprecision(2) << sum << '\n';
    }
    return 0;
}

關鍵點總結

堆疊法巧妙處理運算優先級，無需轉後綴表達式。注意輸入結束條件與換行判斷。