[Leetcode] Basic Calculator 基本计算器

摘要：难点在于多了括号后如何处理正负号。但是每多一个括号，都要记录下这个括号所属的正负号，而每当一个括号结束，我们还要知道出来以后所在的括号所属的正负号。

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