摘要：雙棧法四則運算括號復雜度時間空間思路算符優先算法，核心維護兩個棧，一個操作數棧，一個操作符棧。

Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . 
The integer division should truncate toward zero.
You may assume that the given expression is always valid.
Some examples: "3+2*2" = 7 " 3/2 " = 1 " 3+5 / 2 " = 5 
Note: Do not use the eval built-in library function.

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

算符優先算法，核心維護兩個棧，一個操作數棧，一個操作符棧。
先把輸入tokenize一下，把操作數和操作符分開，注意操作數有可能是多位的如256
依次讀取每個token，兩種情況：
1.是數字，壓入操作數棧
2.是操作符，四種情況：
(1). 當前是加減法，棧頂是加減乘除，則計算棧內直到操作符棧頂不是加減乘除或為空，壓棧；否則直接壓棧
(2). 當前是乘除法，棧頂是乘除，計算直到操作符棧頂不是乘除或為空，壓棧；否則直接壓棧
(3). 當前是左括號，直接壓棧
(4). 當前是右括號，計算直到遇到左括號
當所有token分析完后，循環計算棧頂直到符號棧為空，此時操作數棧里應只有一個元素，也即是最后的結果

先tokenize，不要把字符串處理和計算混在一起，容易思路混亂
模塊化：

tokenize方法把string轉化成token的list
ArrayList tokenize(String s)

計算棧頂
void popAndCal(Stack operators, Stack operands)

計算函數
int exe(int n1, int n2, char op)

public class Solution {
    public int calculate(String s) {
        ArrayList tokens = tokenize(s);
        Stack operators = new Stack();
        Stack operands = new Stack();
        for (int i = 0; i < tokens.size(); i++) {
            String token = tokens.get(i);
            //if token is number
            if (isNumber(token))
                operands.push(Integer.valueOf(token));
            //is operators: (,),+,-,*,/
            else {
                Character cur = token.charAt(0);//convert string to char for operator
                if (operators.isEmpty()) {
                    operators.push(cur);
                } 
                else if (cur == "(") {
                    operators.push(cur);
                }
                else if (cur == ")") {
                    while (operators.peek() != "(") {
                        popAndCal(operators, operands);
                    }
                    operators.pop();
                }
                else if (cur == "+" || cur == "-")  {
                    char top = operators.peek();
                    while (top == "+" || top == "-" || top == "*" || top == "/" ) {
                        popAndCal(operators, operands);
                        top = operators.isEmpty() ? " " : operators.peek();
                    }
                    operators.push(cur);
                }
                else if (cur == "*" || cur == "/") {
                    char top = operators.peek();
                    while (top == "*" || top == "/" ) {
                        popAndCal(operators, operands);
                        top = operators.isEmpty() ? " " : operators.peek();
                    }
                    operators.push(cur);
                }
            }
        }
        while (!operators.isEmpty()) {
            popAndCal(operators, operands);
        }
        return operands.pop();
    }
    
    public boolean isNumber(String s) {
        if (s.charAt(0) <= "9" && s.charAt(0) >= "0")
            return true;
        return false;
    }
    public ArrayList tokenize(String s) {
        ArrayList result = new ArrayList();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length();) {
            if (s.charAt(i) == " ") {
                i++;
                continue;
            }
            else if (!Character.isDigit(s.charAt(i))) {
                result.add(String.valueOf(s.charAt(i++)));
            }
            else {
                sb = new StringBuilder();
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    sb.append(s.charAt(i));
                    i++;
                }
                result.add(sb.toString());
            }
        }
        return result;
    }
    public void popAndCal(Stack operators, Stack operands) {
        int num2 = operands.pop();
        int num1 = operands.pop();
        char opr = operators.pop();
        operands.push(exe(num1, num2, opr));
    }
    public int exe(int n1, int n2, char op) {
        int result = 0;
        if (op == "+") {
            result = n1 + n2;
        }
        else if (op == "-") {
            result = n1 - n2;
        }
        else if (op == "*") {
            result = n1 * n2;
        }
        else if (op == "/") {
            result = n1 / n2;
        }
        return result;
    }
}

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

Expression Add Operators的方法
這題考察的核心是在1+2*3這種，要先算后面的乘法
在1+2的時候，我們要留心后面會出現乘法，所以在計算當前結果的同時(eval=1+2=3)，要把toSubtract(算到1+2的時候toSubtract是2，eval是3)記錄下來傳給后面以便出現乘法可以利用。
那么這個toSubtract什么意思呢，就是如果后面出現了乘法，我可以用eval-toSubtract這樣來還原乘法發生之前的樣子(3-2=1)，用這個數(1)加上我的乘法(2*3)，即1+(2*3)=7，記錄eval=7，表示當前(算到乘以3了)的值，然后把這個乘積(2*3)記為toSubtract
為什么？因為后面如果再出現一個乘以四，即：1+2*3*4，toSubtract應該是2*3=6，這樣可以eval-toSubtract = 7 - 6=1還原乘法之前，1再加上toSubtract(為當前的累積=2*3=6)乘以當前數(4)最后得出1+24=25.

總結：

eval為當前表達式的值，不管后面是什么

toSubtract為提防后面有乘法預留的過程數，他的取值分為兩種情況：

做完加法例如1+2，更新toSub為2；做完減法例如1-2，更新toSub為-2，即加減法toSub為最新的加數/減數；

做完乘法例如1*2，更新toSub為1*2，因為后面如果還有乘法的話要一口氣減掉1*2;再例如，1*2*3*4*5，此時toSubtract為1*2*3*4*5

public int calculate(String s) {
        ArrayList tokens = tokenize(s);
        int toSubtract = 0;
        int eval = 0;
        char operation = "+";
        for (String token : tokens) {
            if (isNumber(token)) {
                int n = Integer.valueOf(token);
                if (operation == "+") {
                    eval = eval + n;
                    toSubtract = n;
                }
                else if (operation == "-") {
                    eval = eval - n;
                    toSubtract = -1 * n;
                }
                else if (operation == "*") {
                    eval = eval - toSubtract + toSubtract * n;
                    toSubtract = toSubtract * n;
                }
                else if (operation == "/") {
                    eval = eval - toSubtract + toSubtract / n;
                    toSubtract = toSubtract / n;
                }
            }
            else
                operation = token.charAt(0);
        }
        return eval;
    }