LeetCode 227：Basic Calculator II — 兩遍掃描處理乘除優先級

題目

實現基本計算器求值，字符串包含非負整數、+ - * /、空格。整數除法向零截斷。不使用 eval。

範例

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

思路：兩遍掃描

1. 第一遍：處理 * 和 /，將乘除算式即時計算並壓入列表，+ - 直接壓入操作數與運算符。
2. 第二遍：對列表中剩下的 + - 從左到右順序計算。

Java 實現（LinkedList 模擬棧/隊列）

public class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) return 0;
        LinkedList nums = new LinkedList<>();
        char op = '+';  // 上一個運算符，初始視為 '+'
        int cur = 0;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                cur = cur * 10 + (c - '0');
            }
            if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
                switch (op) {
                    case '+': nums.addLast(cur); break;
                    case '-': nums.addLast(-cur); break;
                    case '*': nums.addLast(nums.pollLast() * cur); break;
                    case '/': nums.addLast(nums.pollLast() / cur); break;
                }
                op = c;
                cur = 0;
            }
        }
        int res = 0;
        for (int n : nums) res += n;
        return res;
    }
}

關鍵細節

• op 保存上一個運算符，當前數字 cur 讀完後根據 op 決定如何入列表。
• * / 直接與列表尾部數字運算（pollLast），實現優先級提升。
• 最後遍歷列表求和，完成加減。
• 除法向零截斷：Java/C++ 整數除法天然符合。

複雜度

• 時間：O(n)，單次掃描 + 列表遍歷。
• 空間：O(n)，列表存儲中間操作數。

擴展：支持括號

遇到 ( 遞歸調用 calculate 處理子表達式，遇到 ) 返回。需維護索引引用或迭代器。