實作一個基本計算機，求含
+ - * /與非負整數、空白的字串運算式之值（無括號）。整數除法向零取整。例如"3+2*2" = 7、"3/2" = 1、" 3+5 / 2 " = 5。
Example:
Input: s = “3+2*2” Output: 7
Input: s = ” 3/2 ” Output: 1
Input: s = “3+5 / 2” Output: 5
Intuition
TIP
核心思路：用堆疊延後加總。遇到 * / 立刻和堆疊頂端結算（高優先），+ - 則把數字（或其負值）壓入待加；最後把堆疊全部加起來。
- 掃描時累積目前數字
num，遇到下一個運算子（或字串結尾）才結算「前一個運算子」 +→ pushnum；-→ push-num；*//→ pop 出頂端與num運算再 push- 乘除即時和棧頂結算，等於落實了「先乘除後加減」
- 最後堆疊內全是待加項，sum 即答案
Approaches
⭐ 1. Stack Deferred Sum — O(n) / O(n)
- Idea: 記住前一個運算子
op，碰到新運算子時依op結算num - Time:
O(n)- 掃描字串一次 - Space:
O(n)- 堆疊最多存所有加減項
class Solution {
fun calculate(s: String): Int {
val stack = ArrayDeque<Int>()
var num = 0
var op = '+' // 前一個運算子，初始視為 +
for (i in s.indices) {
val c = s[i]
if (c.isDigit()) num = num * 10 + (c - '0')
// 碰到運算子或走到結尾就結算前一個 op
if ((!c.isDigit() && c != ' ') || i == s.length - 1) {
when (op) {
'+' -> stack.addLast(num)
'-' -> stack.addLast(-num)
'*' -> stack.addLast(stack.removeLast() * num)
'/' -> stack.addLast(stack.removeLast() / num)
}
op = c
num = 0
}
}
return stack.sum()
}
}2. O(1) Space: Track Only Previous Term — O(n) / O(1)
- Idea: 堆疊裡其實只有「上一項」會被乘除修改，用一個變數
prev取代堆疊 - Time:
O(n) - Space:
O(1)- 不用堆疊
class Solution {
fun calculate(s: String): Int {
var result = 0
var prev = 0 // 上一個待加入 result 的項
var num = 0
var op = '+'
for (i in s.indices) {
val c = s[i]
if (c.isDigit()) num = num * 10 + (c - '0')
if ((!c.isDigit() && c != ' ') || i == s.length - 1) {
when (op) {
'+' -> { result += prev; prev = num }
'-' -> { result += prev; prev = -num }
'*' -> prev *= num
'/' -> prev /= num
}
op = c
num = 0
}
}
return result + prev
}
}🔑 Takeaways
- Pattern: 堆疊處理運算式優先序——把
* /即時結算、+ -延後加總 - Key trick: 「結算前一個運算子」的迴圈寫法（在遇到新運算子或結尾時觸發）；含括號的 224 Basic Calculator 可在此基礎上用堆疊保存括號外的部分結果