給定一個字串陣列
tokens代表逆波蘭表示法 (RPN) 的算術運算式，計算並回傳結果。有效運算子為+、-、*、/，除法向零截斷。
Example:
Input: tokens = [“2”,“1”,”+”,“3”,”*”] Output: 9 （即 (2 + 1) * 3）
Intuition
TIP
核心思路：RPN 的求值天然適合用堆疊——遇到數字壓入，遇到運算子彈出兩個數計算後壓回。
- 逆波蘭表示法不需要括號，因為運算順序由 token 順序決定
- 遇到運算子時，棧頂第一個彈出的是右運算元，第二個是左運算元（順序很重要，影響減法和除法）
- 遍歷完所有 token 後，堆疊中恰好剩一個元素就是答案
Approaches
1. Recursion (Reverse Parse) — O(n) / O(n)
- Idea: 從 tokens 末尾開始，遇到運算子就遞迴求左右子樹；遇到數字就直接回傳
- Time:
O(n)- 每個 token 處理一次 - Space:
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 — O(n) / O(n)
- Idea: 遍歷 tokens，數字壓入堆疊，遇到運算子彈出兩個數計算後將結果壓回
- Time:
O(n)- 遍歷一次 tokens - Space:
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()
}
}WARNING
注意彈出順序：先彈出的是右運算元 b，後彈出的是左運算元 a。a - b 和 a / b 的順序弄反會得到錯誤結果。Kotlin 的 Int 除法預設就是向零截斷，符合題意。
🔑 Takeaways
- Pattern: RPN 求值是 Stack 的經典教科書應用
- Key trick: 遇到「後綴表達式」或「需要暫存中間結果」的場景，想到 Stack；注意運算元的彈出順序對非交換運算（減、除）很關鍵