150. Evaluate Reverse Polish Notation

題目 / Problem

中文 給你一個字串陣列 tokens，它表示一個用「逆波蘭表示法」(Reverse Polish Notation, RPN) 寫成的算式。請你計算並回傳這個算式的結果（一個整數）。

說明： - 合法的運算子是 '+'、'-'、'*'、'/'。 - 每個運算元可能是整數，或是另一個（已算好的）子算式的結果。 - 兩個整數相除時，結果一律「向 0 取整」（truncate toward zero），例如 13 / 5 = 2、-7 / 2 = -3。 - 保證不會出現除以 0。 - 輸入一定是合法的逆波蘭算式。 - 答案和所有中間計算結果都能用 32 位元整數表示。

English You are given an array of strings tokens representing an arithmetic expression in Reverse Polish Notation (RPN). Evaluate it and return the resulting integer.

Notes: - Valid operators are '+', '-', '*', '/'. - Each operand is either an integer or the result of another sub-expression. - Integer division truncates toward zero (e.g. 13 / 5 = 2). - No division by zero will occur, and the input is always a valid RPN expression. - Every value (answer and intermediate) fits in a 32-bit integer.

Constraints - 1 <= tokens.length <= 10^4 - Each tokens[i] is either an operator ("+", "-", "*", "/") or an integer in [-200, 200].

Worked example Input: tokens = ["2","1","+","3","*"] Output: 9 Explanation: ((2 + 1) * 3) = 9

名詞解釋 / Glossary

• 逆波蘭表示法 / Reverse Polish Notation (RPN)：一種把運算子寫在它的兩個運算元「後面」的算式寫法。例如平常寫 2 + 1，RPN 寫成 2 1 +。好處是不需要括號，也不用考慮運算優先順序。
• 運算元 / Operand：被運算的數字，例如 2 和 1。
• 運算子 / Operator：執行運算的符號，例如 +、-、*、/。
• 堆疊 / Stack：一種「後進先出 (LIFO, Last-In-First-Out)」的資料結構，像一疊盤子，只能從最上面放 (push) 或拿 (pop)。本題用它來暫存還沒被運算的數字。
• push / 入堆：把一個元素放到堆疊最上面。
• pop / 出堆：把堆疊最上面的元素拿走並取得它的值。
• 向 0 取整 / Truncate toward zero：除法捨去小數部分、直接朝 0 的方向取整。正數往下、負數往上，例如 7/2=3、-7/2=-3。在 C/C++ 中整數除法 / 預設就是這種行為，所以我們不必特別處理。
• atoi / 字串轉整數：C 的標準函式，把像 "13"、"-11" 這樣的字串轉成整數。

思路

中文： 最直覺的想法可能是「先把 RPN 轉成我們熟悉的中綴算式 (例如 (2+1)*3)，再去計算」，但這需要處理括號和優先順序，反而更麻煩。RPN 的精妙之處在於：它天生就適合用堆疊一次掃描完成，不需要任何回頭或轉換。關鍵觀察是——當我們從左到右讀 token 時，數字總是「等著」後面的運算子來使用，而運算子一出現，它需要的正是「最近剛讀到的兩個數字」。「最近的兩個」這個特性正好對應堆疊的「後進先出」。所以演算法是：準備一個空堆疊，從左到右掃描每個 token。如果是數字，就把它 push 進堆疊；如果是運算子，就 pop 出兩個數字（注意：先 pop 出來的是右運算元，後 pop 出來的是左運算元，因為後進先出），計算 左 運算子 右，再把結果 push 回堆疊。掃描結束後，堆疊裡剩下的唯一一個數字就是答案。為什麼這樣一定對？因為輸入保證是合法的 RPN，所以每個運算子出現時堆疊裡一定至少有兩個數可用，而每次把「兩個數變一個結果」就等於把一個子算式收合成它的值，最後自然只剩總結果。要特別小心減法和除法的順序（不可交換），左右不能搞反。

English: A tempting first idea is to convert the RPN into the familiar infix form like (2+1)*3 and then evaluate that — but that forces you to deal with parentheses and operator precedence, which is more work, not less. The beauty of RPN is that it maps directly onto a single left-to-right pass using a stack, with no conversion needed. The key insight: as we scan tokens left to right, numbers simply wait for a future operator, and when an operator appears it always consumes the two most recently seen numbers. "Most recent" is exactly what a stack's last-in-first-out behavior gives us. So the algorithm is: keep an empty stack; for each token, if it's a number, push it; if it's an operator, pop two numbers (the first popped is the right operand, the second popped is the left operand, because of LIFO order), compute left op right, and push the result back. After the scan, the single remaining value on the stack is the answer. This is guaranteed correct because the input is a valid RPN expression, so whenever an operator appears the stack has at least two values, and each operation collapses one sub-expression into its value — leaving exactly the final total at the end. Be careful with subtraction and division: they are not commutative, so do not swap the left and right operands.

逐步走查 / Walkthrough

Example input: tokens = ["2","1","+","3","*"], expected output 9.

We process tokens left to right. The stack grows to the right (rightmost element is the "top").

掃描結束，堆疊只剩 9，即為答案。 / Scan complete; the stack holds only 9, which is the answer.

注意第 3 步：先 pop 出來的 1 是右運算元，後 pop 出來的 2 是左運算元。對 + 來說順序無所謂，但對 - 和 / 就至關重要。 / Note step 3: the first value popped (1) is the right operand and the second (2) is the left. Order doesn't matter for +, but it is critical for - and /.

Solution — C

// 演算法：用一個整數陣列當作堆疊，從左到右掃描 tokens。
// Algorithm: use an int array as a stack and scan tokens left to right.
// 遇到數字就 push；遇到運算子就 pop 兩個數、計算、再 push 回結果。
// Push numbers; on an operator pop two values, compute, push the result back.
// 掃完後堆疊頂端 (唯一元素) 就是答案。/ At the end the lone stack value is the answer.

#include <stdlib.h>   // 提供 malloc / free / atoi / String to int. (for malloc/free/atoi)
#include <string.h>   // 提供 strcmp 比較字串 / for strcmp to compare strings.

int evalRPN(char** tokens, int tokensSize) {
    // 配置一個堆疊；最壞情況全是數字，所以大小取 tokensSize 就一定夠。
    // Allocate a stack; worst case all tokens are numbers, so tokensSize slots suffice.
    int* stack = (int*)malloc(sizeof(int) * tokensSize);

    int top = 0;  // top 指向「下一個要寫入的位置」，同時等於目前堆疊大小。
                  // top is the next write index, and also the current stack size.

    // 逐一處理每個 token（tokens[i] 是一個字串，即 char*）。
    // Process each token one by one (tokens[i] is a string, i.e. a char*).
    for (int i = 0; i < tokensSize; i++) {
        char* t = tokens[i];  // t 指向目前這個字串 / t points to the current token string.

        // strcmp 回傳 0 代表兩字串完全相同。判斷 t 是否為四個運算子之一。
        // strcmp returns 0 when the two strings are equal. Check if t is an operator.
        if (strcmp(t, "+") == 0 || strcmp(t, "-") == 0 ||
            strcmp(t, "*") == 0 || strcmp(t, "/") == 0) {

            // 是運算子：先 pop 出右運算元（後進先出，最上面的是右邊）。
            // It's an operator: pop the right operand first (LIFO: top is the right side).
            int right = stack[--top];   // --top 先把 top 減 1，再取該位置的值 / pre-decrement then read.

            // 再 pop 出左運算元。/ Then pop the left operand.
            int left = stack[--top];

            int result;  // 存放這次運算的結果 / holds this operation's result.

            // 依運算子計算。t[0] 是字串的第一個字元（運算子只有一個字元）。
            // Compute based on the operator. t[0] is the first character of the string.
            if      (t[0] == '+') result = left + right;
            else if (t[0] == '-') result = left - right;   // 順序重要：左 - 右 / order matters: left - right.
            else if (t[0] == '*') result = left * right;
            else                  result = left / right;   // C 的整數除法本來就向 0 取整 / C int division already truncates toward zero.

            // 把結果 push 回堆疊（寫入 top 位置後 top 加 1）。
            // Push the result back (write at top, then increment top).
            stack[top++] = result;
        } else {
            // 不是運算子 → 是數字。atoi 把字串轉成整數（能處理負號，如 "-11"）。
            // Not an operator → a number. atoi converts the string to int (handles "-11").
            stack[top++] = atoi(t);  // push 該數字 / push the number.
        }
    }

    int answer = stack[0];  // 掃描結束，堆疊只剩一個值，在索引 0 / only one value remains, at index 0.
    free(stack);            // 釋放剛才 malloc 的記憶體，避免記憶體洩漏 / free the malloc'd memory to avoid a leak.
    return answer;          // 回傳答案 / return the answer.
}

Solution — C++

// 演算法：與 C 版相同，用 std::stack<int> 暫存數字。
// Algorithm: same as the C version, using std::stack<int> to hold numbers.
// 數字 push；運算子 pop 兩個、計算、push 回結果；最後堆疊頂端即答案。
// Push numbers; on operators pop two, compute, push back; the final top is the answer.

#include <stack>     // 提供 std::stack 容器 / provides the std::stack container.
#include <string>    // 提供 std::string 與 std::stoi / provides std::string and std::stoi.
#include <vector>    // 函式參數用 vector / parameter uses a vector.

class Solution {
public:
    int evalRPN(std::vector<std::string>& tokens) {
        std::stack<int> st;  // 宣告一個整數堆疊 / declare a stack of ints.

        // range-for：依序取出 tokens 裡的每個字串。const& 避免複製字串。
        // range-for: iterate over each string in tokens. const& avoids copying each string.
        for (const std::string& t : tokens) {

            // 判斷 t 是否為運算子。t == "+" 直接比較字串內容很直觀。
            // Check if t is an operator. std::string supports == for content comparison.
            if (t == "+" || t == "-" || t == "*" || t == "/") {

                int right = st.top();  // top() 看堆疊最上面的值（右運算元）/ top() reads the topmost value (right operand).
                st.pop();              // pop() 移除最上面的值，但本身不回傳 / pop() removes the top; it returns nothing.

                int left = st.top();   // 第二個取出的是左運算元 / the second one taken is the left operand.
                st.pop();

                int result;  // 本次運算結果 / result of this operation.

                // 用第一個字元 t[0] 判斷運算子並計算。
                // Decide and compute using the first character t[0].
                if      (t == "+") result = left + right;
                else if (t == "-") result = left - right;   // 左 - 右，順序不可顛倒 / left - right, order must not flip.
                else if (t == "*") result = left * right;
                else               result = left / right;   // 整數除法向 0 取整，符合題意 / int division truncates toward zero, as required.

                st.push(result);  // 把結果放回堆疊 / push the result back.
            } else {
                // 是數字：std::stoi 把字串轉成 int（可處理負號）。
                // A number: std::stoi parses the string into an int (handles negatives).
                st.push(std::stoi(t));
            }
        }

        return st.top();  // 堆疊僅剩的值就是答案 / the single remaining value is the answer.
    }
};

複雜度 / Complexity

• Time: O(n) — n 是 tokens 的長度。我們只從頭到尾掃描一次，每個 token 做的工作（比較、push、pop、一次四則運算）都是 O(1)。/ n is the number of tokens. We make one pass, and each token does constant work (compare, push/pop, one arithmetic op).
• Space: O(n) — 堆疊最多同時存放所有數字。最壞情況（例如全是數字直到最後才出現運算子）堆疊大小可達約 n/2 以上，屬於 O(n)。/ The stack may hold up to ~n values at once in the worst case, so the extra space is linear in n.

Pitfalls & Edge Cases

• 運算元順序顛倒 / Swapped operand order：因為堆疊是後進先出，先 pop 出的是「右」運算元，後 pop 出的是「左」運算元。對 - 和 / 來說 left - right 與 right - left 結果不同，搞反就會錯。程式碼中明確命名 left、right 來避免混淆。 / The first popped value is the right operand, the second is left. For - and / the order changes the result, so we name them explicitly.
• 除法取整方向 / Division rounding direction：題目要求向 0 取整。C/C++ 的整數 / 本來就是向 0 取整（如 -7/2 = -3），所以不需特別處理；但若你誤用 floor 除法（向負無窮取整）就會在負數時出錯。 / The problem wants truncation toward zero, which is exactly C/C++ integer / behavior; using floor division would be wrong for negatives.
• 把負數誤判成運算子 / Mistaking a negative number for an operator：像 "-11" 是數字不是運算子。我們用「完整字串比較」(strcmp/==) 判斷運算子，而不是「看第一個字元是不是 -」，所以 "-11" 會正確走到 atoi/stoi 分支。 / Tokens like "-11" are numbers. We test for operators by full-string comparison, not by checking the first char, so negatives are parsed correctly.
• 單一數字輸入 / Single-number input：若 tokens = ["42"]，迴圈只 push 一次，最後直接回傳 42。演算法天然支援，無需特例。 / With one number, we just push and return it; no special case needed.
• 溢位 / Overflow：題目保證所有中間與最終結果都在 32 位元整數範圍內，所以用 int 安全；若沒有這個保證，乘法可能溢位需用 long。 / Guaranteed to fit in 32-bit int, so int is safe; without that guarantee multiplication could overflow.