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

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.

時(shí)間 O(N) 空間 O(N)

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

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

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

時(shí)間 O(N) 空間 O(N)

因?yàn)槌朔ê统ú粌H要知道下一個(gè)數(shù)，也要知道上一個(gè)數(shù)。所以我們用一個(gè)棧把上次的數(shù)存起來(lái)，遇到加減法就直接將數(shù)字壓入棧中，遇到乘除法就把棧頂拿出來(lái)乘或除一下新數(shù)，再壓回去。最后我們把棧里所有數(shù)加起來(lái)就行了。

先用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);
            // 拿出下一個(gè)數(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();
    }
    
}

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

這題很像Expression Add Operator。因?yàn)闆](méi)有括號(hào)，其實(shí)我們也可以不用棧。首先維護(hù)一個(gè)當(dāng)前的結(jié)果，加減法的時(shí)候，直接把下一個(gè)數(shù)加上或減去就行了。乘除法的技巧在于，記錄下上次的數(shù)字，這樣我們把上次計(jì)算出的結(jié)果，減去上次的數(shù)字，得到了上上次的結(jié)果，就相當(dāng)于回退到加或減上一個(gè)數(shù)字之前的情況了。這時(shí)候我們?cè)侔焉弦粋€(gè)數(shù)字乘上或除以當(dāng)前的數(shù)字，最后再加或減回上上次的結(jié)果，就是這次的結(jié)果了。比如2+3*4，當(dāng)算完3時(shí)，結(jié)果是5，當(dāng)算到4時(shí)，先用5-3=2，再用2+3*4=14，就是當(dāng)前結(jié)果。這里要注意的是，對(duì)于下一個(gè)數(shù)，它的上一個(gè)數(shù)不是我們這輪的數(shù)，而是我們這輪的上輪的數(shù)乘以或除以這輪的數(shù)，如2+3*4*5，到4的時(shí)候結(jié)果14，到5的時(shí)候，上一個(gè)數(shù)是3*4，而不是4。

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

public class Solution {
    public int calculate(String s) {
        s = s.replace(" ","");
        long currRes = 0, prevNum = 0;
        // 拿出第一個(gè)數(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;
            }
            // 計(jì)算完后，跳過(guò)當(dāng)前的運(yùn)算符和數(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();
    }
    
}