摘要：難點在于多了括號后如何處理正負號。但是每多一個括號，都要記錄下這個括號所屬的正負號，而每當一個括號結束，我們還要知道出來以后所在的括號所屬的正負號。

Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
You may assume that the given expression is always valid.
Some examples:
"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.

時間 O(N) 空間 O(N)

很多人將該題轉換為后綴表達式后（逆波蘭表達式）求解，其實不用那么復雜。題目條件說明只有加減法和括號，由于加減法是相同順序的，我們大可以直接把所有數順序計算。難點在于多了括號后如何處理正負號。我們想象一下如果沒有括號這題該怎們做：因為只有加減號，我們可以用一個變量sign來記錄上一次的符號是加還是減，這樣把每次讀到的數字乘以這個sign就可以加到總的結果中了。有了括號后，整個括號內的東西可一看成一個東西，這些括號內的東西都會受到括號所在區域內的正負號影響（比如括號前面是個負號，然后括號所屬的括號前面也是個負號，那該括號的符號就是正號）。但是每多一個括號，都要記錄下這個括號所屬的正負號，而每當一個括號結束，我們還要知道出來以后所在的括號所屬的正負號。根據這個性質，我們可以使用一個棧，來記錄這些括號所屬的正負號。這樣我們每遇到一個數，都可以根據當前符號，和所屬括號的符號，計算其真實值。

先用String.replace()去掉所有的空格

public class Solution {
    public int calculate(String s) {
        // 去掉所有空格
        s = s.replace(" ", "");
        Stack stk = new Stack();
        // 先壓入一個1進棧，可以理解為有個大括號在最外面
        stk.push(1);
        int i = 0, res = 0, sign = 1;
        while(i < s.length()){
            char c = s.charAt(i);
            // 遇到正號，將當前的符號變為正號
            if(c=="+"){
                sign = 1;
                i++;
            // 遇到負號，將當前的符號變為負號
            } else if(c=="-"){
                sign = -1;
                i++;
            // 遇到左括號，計算當前所屬的符號，壓入棧中
            // 計算方法是當前符號乘以當前所屬括號的符號
            } else if(c=="("){
                stk.push(sign * stk.peek());
                sign = 1;
                i++;
            // 遇到右括號，當前括號結束，出棧
            } else if(c==")"){
                stk.pop();
                i++;
            // 遇到數字，計算其正負號并加入總結果中
            } else {
                int num = 0;
                while(i < s.length() && Character.isDigit(s.charAt(i))){
                    num = num * 10 + s.charAt(i) - "0";
                    i++;
                }
                res += num * sign * stk.peek();
            }
        }
        return res;
    }
}

時間 O(N) 空間 O(N)

因為乘法和除法不僅要知道下一個數，也要知道上一個數。所以我們用一個棧把上次的數存起來，遇到加減法就直接將數字壓入棧中，遇到乘除法就把棧頂拿出來乘或除一下新數，再壓回去。最后我們把棧里所有數加起來就行了。

先用String.replace()去掉所有的空格

public class Solution {
    public int calculate(String s) {
        s = s.replace(" ", "");
        Stack stk = new Stack();
        String firstNum = getNum(0, s);
        stk.push(Long.parseLong(firstNum));
        int i = firstNum.length();
        while(i < s.length()){
            char c = s.charAt(i);
            // 拿出下一個數字
            String numStr = getNum(i + 1, s);
            if(c == "+"){
                stk.push(Long.parseLong(numStr));
            }
            if(c == "-"){
                stk.push(-Long.parseLong(numStr));
            }
            if(c == "*"){
                stk.push(stk.pop()*Long.parseLong(numStr));
            }
            if(c == "/"){
                stk.push(stk.pop()/Long.parseLong(numStr));
            }
            i = i+ numStr.length() + 1;
        }
        long res = 0;
        while(!stk.isEmpty()){
            res += stk.pop();
        }
        return (int)res;
    }
    
    private String getNum(int i, String s){
        StringBuilder num = new StringBuilder();
        while(i < s.length() && Character.isDigit(s.charAt(i))){
            num.append(s.charAt(i));
            i++;
        }
        return num.toString();
    }
    
}

時間 O(N) 空間 O(1)

這題很像Expression Add Operator。因為沒有括號，其實我們也可以不用棧。首先維護一個當前的結果，加減法的時候，直接把下一個數加上或減去就行了。乘除法的技巧在于，記錄下上次的數字，這樣我們把上次計算出的結果，減去上次的數字，得到了上上次的結果，就相當于回退到加或減上一個數字之前的情況了。這時候我們再把上一個數字乘上或除以當前的數字，最后再加或減回上上次的結果，就是這次的結果了。比如2+3*4，當算完3時，結果是5，當算到4時，先用5-3=2，再用2+3*4=14，就是當前結果。這里要注意的是，對于下一個數，它的上一個數不是我們這輪的數，而是我們這輪的上輪的數乘以或除以這輪的數，如2+3*4*5，到4的時候結果14，到5的時候，上一個數是3*4，而不是4。

要多帶帶處理第一個數的情況

public class Solution {
    public int calculate(String s) {
        s = s.replace(" ","");
        long currRes = 0, prevNum = 0;
        // 拿出第一個數
        String firstNum = getNum(0, s);
        currRes = Long.parseLong(firstNum);
        prevNum = currRes;
        int i = firstNum.length();
        while(i < s.length()){
            char c = s.charAt(i);
            String numStr = getNum(i + 1, s);
            System.out.println(numStr);
            long n = Long.parseLong(numStr);
            if(c == "+"){
                currRes += n;
                prevNum = n;
            }
            if(c == "-"){
                currRes -= n;
                prevNum = -n;
            }
            if(c == "*"){
                // 上次的結果，減去上次的數，再加上上次的數乘以這次的數，就是這次的結果
                currRes = currRes - prevNum + prevNum * n;
                prevNum = prevNum * n;
            }
            if(c == "/"){
                // 上次的結果，減去上次的數，再加上上次的數除以這次的數，就是這次的結果
                currRes = currRes - prevNum + prevNum / n;
                prevNum = prevNum / n;
            }
            // 計算完后，跳過當前的運算符和數字
            i = i + numStr.length() + 1;
        }
        return (int)currRes;
    }
    
    private String getNum(int i, String s){
        StringBuilder num = new StringBuilder();
        while(i < s.length() && Character.isDigit(s.charAt(i))){
            num.append(s.charAt(i));
            i++;
        }
        return num.toString();
    }
    
}