[Leetcode] Basic Calculator/Evaluate Expression 设

摘要：双栈法四则运算括号复杂度时间空间思路算符优先算法，核心维护两个栈，一个操作数栈，一个操作符栈。

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;
    }