150. Evaluate Reverse Polish Notation

📘 題目敘述

給你一個字串陣列 tokens，表示一個 Reverse Polish Notation 的算術表達式。

請計算這個表達式的值，並回傳其整數結果。

注意：

• 合法運算子只有 '+'、'-'、'*' 和 '/'
• 每個運算元可能是一個整數，也可能是另一個表達式的結果
• 兩個整數相除時，一律朝 0 截斷
• 不會出現除以 0 的情況
• 輸入一定是一個合法的 reverse polish notation 表達式
• 最後答案與中間計算結果都保證可以用 32-bit 整數表示

條件限制

• 1 <= tokens.length <= 10^4
• tokens[i] 可能是運算子 "+"、"-"、"*"、"/"，或是一個介於 [-200, 200] 的整數

🧠 解題思路

這題是很典型的 stack 題。

Reverse Polish Notation 的特點是：

• 數字先出現
• 運算子出現時，就拿前面的結果來算

所以我用一個 stack 來存「目前已經讀過、但還沒被更上層運算消耗掉的數值」。

掃 tokens 時分兩種情況：

• 如果目前這個 token 是數字
  • 直接轉成整數後 push 進 stack
• 如果目前這個 token 是運算子
  • 就從 stack 最上面拿出兩個數字做運算
  • 再把結果 push 回去

這裡最重要的是順序。

因為 stack 是後進先出，所以：

• 第一個 pop 出來的是右邊的數
• 第二個 pop 出來的是左邊的數

所以程式裡：

• x 是右操作數
• y 是左操作數

這在減法和除法特別重要，因為：

• 要算的是 y - x
• 不是 x - y
• 要算的是 y / x
• 不是 x / y

整個掃描結束後，stack 裡最後剩下的那個值，就是整個 RPN 表達式的答案。

也就是說，這題的核心就是：

用 stack 存還沒被合併的數值，遇到數字就 push，遇到運算子就 pop 兩個數來計算，再把結果 push 回去。

所有變數

• s：stack，存目前尚未被更外層運算消耗掉的數值
• x：從 stack 最上面 pop 出來的第一個數，代表右操作數
• y：再 pop 出來的第二個數，代表左操作數

🪜 主要流程步驟

1. 先建立一個 stack 來存計算中的數值

stack<int> s;

這個 stack 的用途是：

• 遇到數字時先存起來
• 遇到運算子時，再把需要的兩個數字拿出來算

所以它就是整份程式的核心資料結構。

2. 依序掃過每一個 token

for (string i : tokens) {

這裡把 tokens 裡的每個字串依序取出。

因為 Reverse Polish Notation 本來就是要照順序讀，所以直接從左到右掃一遍就可以。

3. 如果目前 token 是數字，就直接 push 進 stack

if (i != "+" && i != "-" && i != "*" && i != "/") {
    s.push(stoi(i));
    continue;
}

這段是在判斷：

• 如果目前這個 token 不是四種運算子之一
• 那它就是一個整數

這時就把它用 stoi(i) 轉成 int，然後 push 進 stack。

continue 的意思是：

• 這個 token 已經處理完了
• 直接進下一輪，不用繼續往下判斷運算子

4. 如果目前 token 是運算子，就 pop 出兩個數字

int x = s.top();
s.pop();
int y = s.top();
s.pop();

這一步是整題最重要的地方。

因為 RPN 遇到運算子時，要拿前面最近的兩個運算元來算。

但 stack 是後進先出，所以：

• 第一個 pop 出來的是右邊的數 x
• 第二個 pop 出來的是左邊的數 y

這個順序不能搞反，尤其是：

• 減法要算 y - x
• 除法要算 y / x

如果反過來就錯了。

5. 根據運算子做對應運算，再把結果 push 回去

這裡就是把剛剛拿出來的兩個數字合併成一個新結果。

不同運算子分別做：

• +：y + x
• -：y - x
• *：y * x
• /：y / x

算完後再把結果 push 回 stack。

這表示：

• 這個子表達式已經被化簡成一個值
• 之後如果還有更外層運算，可以再把這個結果當成普通數字繼續使用

6. 為什麼最後 stack 只會剩一個值

因為題目保證：

• 輸入一定是合法的 RPN 表達式

所以每次遇到運算子時，stack 裡一定會有足夠的兩個數字可以拿來算。

而且每做一次運算：

• stack 先 pop 兩個
• 再 push 一個結果

等於 stack 元素數量少一個。

最後整個表達式全部化簡完後，就只會剩下一個值，這個值就是整個表達式的答案。

7. 最後回傳 stack 最上面的值

return s.top();

當所有 token 都處理完後，s.top() 就是最後答案，直接回傳即可。

⏱️ 複雜度

設 n = tokens.length。

• 時間複雜度：O(n)
  每個 token 只會被處理一次。
• 空間複雜度：O(n)
  最壞情況下 stack 可能暫時存下線性數量的數值。

💻 程式碼實作

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> s;
        for (string i : tokens) {
            if (i != "+" && i != "-" && i != "*" && i != "/") {
                s.push(stoi(i));
                continue;
            }
            int x = s.top();
            s.pop();
            int y = s.top();
            s.pop();
            if (i == "+") {
                s.push(y + x);
            } else if (i == "-") {
                s.push(y - x);
            } else if (i == "*") {
                s.push(y * x);
            } else {
                s.push(y / x);
            }
        }
        return s.top();
    }
};

🔗 題目連結

https://leetcode.com/problems/evaluate-reverse-polish-notation/