150. Evaluate Reverse Polish Notation

Medium

Description

給定一個字串陣列 tokens 代表逆波蘭表示法 (RPN) 的算術運算式，計算並回傳結果。有效運算子為 +、-、*、/，除法向零截斷。

Example:

Input: tokens = [“2”,“1”,"+",“3”,"*"] Output: 9 （即 (2 + 1) * 3）

Intuition#

核心思路：RPN 的求值天然適合用堆疊——遇到數字壓入，遇到運算子彈出兩個數計算後壓回。

逆波蘭表示法不需要括號，因為運算順序由 token 順序決定
遇到運算子時，棧頂第一個彈出的是右運算元，第二個是左運算元（順序很重要，影響減法和除法）
遍歷完所有 token 後，堆疊中恰好剩一個元素就是答案

Approaches#

1: 遞迴（反向解析）#

概念: 從 tokens 末尾開始，遇到運算子就遞迴求左右子樹；遇到數字就直接回傳
時間複雜度: O(n) - 每個 token 處理一次
空間複雜度: O(n) - 遞迴深度

class Solution {
    private var index = 0

    fun evalRPN(tokens: Array<String>): Int {
        index = tokens.size - 1
        return evaluate(tokens)
    }

    private fun evaluate(tokens: Array<String>): Int {
        val token = tokens[index--]
        if (token !in setOf("+", "-", "*", "/")) {
            return token.toInt()
        }
        val right = evaluate(tokens)
        val left = evaluate(tokens)
        return when (token) {
            "+" -> left + right
            "-" -> left - right
            "*" -> left * right
            "/" -> left / right
            else -> throw IllegalArgumentException()
        }
    }
}

⭐2: Stack#

概念: 遍歷 tokens，數字壓入堆疊，遇到運算子彈出兩個數計算後將結果壓回
時間複雜度: O(n) - 遍歷一次 tokens
空間複雜度: O(n) - 堆疊最多存 n/2 個數

class Solution {
    fun evalRPN(tokens: Array<String>): Int {
        val stack = ArrayDeque<Int>()

        for (token in tokens) {
            when (token) {
                "+", "-", "*", "/" -> {
                    val b = stack.removeLast()
                    val a = stack.removeLast()
                    val result = when (token) {
                        "+" -> a + b
                        "-" -> a - b
                        "*" -> a * b
                        "/" -> a / b
                        else -> throw IllegalArgumentException()
                    }
                    stack.addLast(result)
                }
                else -> stack.addLast(token.toInt())
                }
        }

        return stack.last()
    }
}

注意彈出順序：先彈出的是右運算元 b，後彈出的是左運算元 a。a - b 和 a / b 的順序弄反會得到錯誤結果。Kotlin 的 Int 除法預設就是向零截斷，符合題意。

🔑 Takeaways#

Pattern: RPN 求值是 Stack 的經典教科書應用
關鍵技巧: 遇到「後綴表達式」或「需要暫存中間結果」的場景，想到 Stack；注意運算元的彈出順序對非交換運算（減、除）很關鍵