227. Basic Calculator II - Medium

前往題目

想法

• 用stack，只壓入數字和+-，乘除直接用stack最上層的數字計算就可以

思路

沒看到數字不一定是一個digit

1. 疊代整個string
2. 每次判斷是否為數字，如果是則看有多少位，把整串擷取，然後看是什麼operator做相應的計算(如果是整個運算式的第一個數字那就會剛好直接加入)
3. 如果不是數字，也不是空格，那就一定是operator，紀錄

Code

這個解法沒有用到stack，空間只要O(1)，理解起來也很簡單，只是有非常多細節的地方需要注意…

class Solution {
    public int calculate(String s) {
        int i = 0;

        int cur = 0, prev = 0, res = 0;
        char operator = '+';

        while (i < s.length()) {
            char curChar = s.charAt(i);

            if (Character.isDigit(curChar)) {
                // Assemble numbers
                while (i < s.length() && 
                        Character.isDigit(s.charAt(i))) {
                    cur = cur * 10 + (s.charAt(i) - '0');
                    ++i;
                }
                --i; // Prevent out of bound

                if (operator == '+') {
                    res += cur; // Add to result
                    prev = cur; // Update previous number
                } else if (operator == '-') {
                    res -= cur;
                    prev = -cur; // Update
                } else if (operator == '*') {
                    res -= prev; // Undo
                    res += prev * cur;
                    prev = prev * cur;
                } else {
                    res -= prev;
                    res += prev / cur;
                    prev = prev / cur;
                }

                cur = 0; // reset current number
            } else if (curChar != ' ') {
                operator = curChar;
            }
            
            ++i;
        }
        return res;
    }
}