LeetCode 筆記：Evaluate Reverse Polish Notation（逆波蘭表達式求值）

題目描述

計算逆波蘭表示法（後綴表達式）的值。運算符 +, -, *, /，運算元為整數或子表達式。例：[2,1,+,3,*] → ((2+1)*3) → 9。

逆波蘭式原理

後綴表達式將運算符放在運算元之後。規則：

1. 變數/常數本身即後綴式。
2. E1 op E2 後綴為 E1, E2, op。
3. (E1) 後綴同 E1。

計算機用堆疊：遇運算元入棧，遇運算符彈出兩元素運算，結果入棧。(a+b)*c → ab+c* 過程圖解：

1. a 入棧
2. b 入棧
3. 遇 +：彈出 a,b → 計算 a+b → 結果 d 入棧
4. c 入棧
5. 遇 *：彈出 d,c → 計算 d*c → 結果 e 入棧
6. 最終棧頂 e 為結果

C++ 實現

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

class Solution {
    int str2int(string s) {
        int result = 0, base = 1, sign = 1;
        if (s[0] == '-') sign = -1;
        for (int i = s.size() - 1; i >= 0; --i)
            if (isdigit(s[i])) { result += base * (s[i] - '0'); base *= 10; }
        return result * sign;
    }
public:
    int evalRPN(vector<string> &tokens) {
        stack<int> st;
        for (auto &t : tokens) {
            if (t == "+" || t == "-" || t == "*" || t == "/") {
                int n2 = st.top(); st.pop();
                int n1 = st.top(); st.pop();
                if (t == "+") st.push(n1 + n2);
                else if (t == "-") st.push(n1 - n2);
                else if (t == "*") st.push(n1 * n2);
                else st.push(n1 / n2);
            } else st.push(str2int(t));
        }
        return st.top();
    }
};

關鍵細節

• 彈出順序：先彈出的是右運算元，再彈出左運算元。
• 字串轉整數需處理正負號。
• 除法為整數除法，截斷向零。
• 邊界：單一運算元、空輸入等。