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

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)

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

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

public class Solution {
    public int calculate(String s) {
        // 去掉所有空格
        s = s.replace(" ", "");
        Stack stk = new Stack();
        // 先壓入一個1進(jìn)棧，可以理解為有個大括號在最外面
        stk.push(1);
        int i = 0, res = 0, sign = 1;
        while(i < s.length()){
            char c = s.charAt(i);
            // 遇到正號，將當(dāng)前的符號變?yōu)檎?            if(c=="+"){
                sign = 1;
                i++;
            // 遇到負(fù)號，將當(dāng)前的符號變?yōu)樨?fù)號
            } else if(c=="-"){
                sign = -1;
                i++;
            // 遇到左括號，計算當(dāng)前所屬的符號，壓入棧中
            // 計算方法是當(dāng)前符號乘以當(dāng)前所屬括號的符號
            } else if(c=="("){
                stk.push(sign * stk.peek());
                sign = 1;
                i++;
            // 遇到右括號，當(dāng)前括號結(jié)束，出棧
            } else if(c==")"){
                stk.pop();
                i++;
            // 遇到數(shù)字，計算其正負(fù)號并加入總結(jié)果中
            } 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)

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

先用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);
            // 拿出下一個數(shù)字
            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。因為沒有括號，其實我們也可以不用棧。首先維護(hù)一個當(dāng)前的結(jié)果，加減法的時候，直接把下一個數(shù)加上或減去就行了。乘除法的技巧在于，記錄下上次的數(shù)字，這樣我們把上次計算出的結(jié)果，減去上次的數(shù)字，得到了上上次的結(jié)果，就相當(dāng)于回退到加或減上一個數(shù)字之前的情況了。這時候我們再把上一個數(shù)字乘上或除以當(dāng)前的數(shù)字，最后再加或減回上上次的結(jié)果，就是這次的結(jié)果了。比如2+3*4，當(dāng)算完3時，結(jié)果是5，當(dāng)算到4時，先用5-3=2，再用2+3*4=14，就是當(dāng)前結(jié)果。這里要注意的是，對于下一個數(shù)，它的上一個數(shù)不是我們這輪的數(shù)，而是我們這輪的上輪的數(shù)乘以或除以這輪的數(shù)，如2+3*4*5，到4的時候結(jié)果14，到5的時候，上一個數(shù)是3*4，而不是4。

要多帶帶處理第一個數(shù)的情況

public class Solution {
    public int calculate(String s) {
        s = s.replace(" ","");
        long currRes = 0, prevNum = 0;
        // 拿出第一個數(shù)
        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 == "*"){
                // 上次的結(jié)果，減去上次的數(shù)，再加上上次的數(shù)乘以這次的數(shù)，就是這次的結(jié)果
                currRes = currRes - prevNum + prevNum * n;
                prevNum = prevNum * n;
            }
            if(c == "/"){
                // 上次的結(jié)果，減去上次的數(shù)，再加上上次的數(shù)除以這次的數(shù)，就是這次的結(jié)果
                currRes = currRes - prevNum + prevNum / n;
                prevNum = prevNum / n;
            }
            // 計算完后，跳過當(dāng)前的運算符和數(shù)字
            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();
    }
    
}