題目描述:給定以逆波蘭表示法(後綴表示法)寫成的算術表達式 tokens,計算並回傳其結果。支援的運算子為 +、-、*、/(整數除法,向零截斷)。
解題思路:逆波蘭表示法的特點是運算子出現在兩個運算元之後,天然適合用堆疊處理。遍歷 tokens:遇到數字則推入堆疊;遇到運算子則從堆疊彈出兩個運算元(注意先彈出的是右運算元,後彈出的是左運算元),執行對應運算後將結果推回堆疊。遍歷結束後堆疊頂端即為最終結果。
時間複雜度:O(n) — 每個 token 恰好被處理一次,堆疊操作均為 O(1)。
空間複雜度:O(n) — 堆疊最多儲存約 (n+1)/2 個運算元(全為數字的情況)。
1. Create empty stack
2. For each token in tokens:
a. If token is an operator (+, -, *, /):
- Pop b (right operand), then pop a (left operand)
- Compute result = a op b
- Push result onto stack
b. Else: parse token as integer and push onto stack
3. Return stack.top()遞迴(後序遍歷) O(n):從後往前遞迴解析,遇到運算子時遞迴求兩個子表達式的值。概念上等價但呼叫堆疊佔用 O(n) 空間且不如迭代直觀。
轉換為樹結構:先建立抽象語法樹(AST),再後序遍歷求值。結構清晰但建樹本身需要額外 O(n) 空間和時間,對此題過度設計。
^)或一元負號(~),程式碼需如何修改?3 + 4 * 2)轉換為逆波蘭表示法(Shunting-yard 演算法)?long long 的策略是否仍適用?