4.7拆解复杂问题-实现计算器

4.7 拆解复杂问题:实现计算器

• 表达式求值算法是一个Hard级别的问题，最终实现一个包含如下功能的计算器
• 输入一个字符串，可以包含+ - * /、数字、空格、算法返回运算结果
• 要符合运算法则，括号的优先级最高，先乘除再加减
• 除号是整数除法，无论正负都向0取整(5/2=2,-5/2=-2)
• 可以假定输入的算式是一定合法的，而且计算过程不会出现整形溢出，不会出现除数为0的exception

4.7.1 字符串转整数

• 在JAVA中提供了现成的API对字符串进行解析

        Integer.parseInt(s);
1

4.7.2 处理加减法

如果输入的这个算式只包含加减法，而且不存在空格，该如何计算结果呢?我们先手工计算一下算式1-12+3为例，来说一个很简单的思路

• 先给第一个数字加一个默认符号+，变成+1-12+3
• 把一个运算符和数字组合成一对，也就是三对+1,-12,+3,把它转化成数字，然后放到一个栈中
• 最后将栈中的所有数字进行求和，就是原算式的结果

    public int calculate(String s) {
        Integer.parseInt(s);
        Stack<Integer> stack = new Stack<>();
        //记录算式中的数字
        int num = 0;
        //记录num前的符号,初始化为+
        char sign = '+';
        for(int i = 0;i<s.length();i++){
            char c = s.charAt(i);
            //如果是数字,就连续读取出来
            if(Character.isDigit(c)){
                num = 10*num + (c-'0');
            }
            //如果不是数字,就证明遇到了下一个符号
            //之前的数字和符号就要存进栈中
            //存栈这个操作 还要在字符串遍历结束之后再来一次
            if(!Character.isDigit(c) || i == s.length()-1 ){
                switch (sign){
                    case '+':
                        stack.push(num);break;
                    case '-':
                        stack.push(-num);break;
                }
                //更新符号为当前符号,数字清零
                sign = c;
                num=0;
            }
        }
        //将栈中的所有结果进行求和
        int res = 0;
        while (!stack.isEmpty()){
            res += stack.peek();
            stack.pop();
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

4.7.3 处理乘除法

• 其实思路和仅处理加减法是没有区别的，拿字符串2-3*4+5举例，核心思路依然是把字符串分解成符号和数字的组合，比如说上述例子就可以分解为+2、-3、*4、+5几对，接下来其实思考一下发现其实就是switch中的处理不同而已，因此我们只需要修改switch里面的内容就可以了

                    //只需要拿出前一个数字做对应的运算即可
                    case '*':
                        pre = stack.peek();stack.pop();
                        stack.push(pre*num);
                        break;
                    case '/':
                        pre = stack.peek();stack.pop();
                        stack.push(pre/num);
                        break;
1
2
3
4
5
6
7
8
9

• 但是这时候有个疑问，这样做是否能够保证乘除法的优先性呢?

• 乘除法的优先性体现于在:乘除法可以和栈顶的元素结合然后把结果加入栈，而加减法只能把自己加入栈

• 也可以这么理解，运算顺序问题，当遇到*和/的时候都是在case里面就完成的，而+和-都是在后面完成的

4.7.4 处理空格

 if((!Character.isDigit(c) && c!=' ') || i == s.length()-1 )
1

• 只需要加上该条件即可自动跳过空格而不处理了

4.7.5 处理括号

• 无论括号嵌套多少层，都可以使用一个递归辅助函数来搞定

• 可以这么说的依据是，计算括号的过程都是完全一样的，具有一个base-case(没有括号的情况)，而且如果括号嵌套的话，可以通过一个base-case逐渐状态转移到之后的状态，以字符串3*(4-5/2)-6举例:

• calculate(3*(4-5/2)-6) = 3*calculate(4-5/2)-6 = 0

• 换句话说，括号包含的等式，直接视作为一个数字就可以了

• 递归开始的条件:遇到(就开始递归，遇到)就结束递归

    public int calculate(String s) {
        return helper(new StringBuilder(s));
    }

    private int helper(StringBuilder s){
        Stack<Integer> stack = new Stack<>();
        //记录算式中的数字
        int num = 0;
        //记录num前的符号,初始化为+
        char sign = '+';
        while(s.length()>0){
            char c = s.charAt(0);
            s = s.delete(0, 1);
            //如果是数字,就连续读取出来
            if(Character.isDigit(c)){
                num = 10*num + (c-'0');
            }
            //如果不是数字,就证明遇到了下一个符号
            //之前的数字和符号就要存进栈中
            //存栈这个操作 还要在字符串遍历结束之后再来一次
            if(c == '('){
                num = helper(s);
            }
            if((!Character.isDigit(c) && c!=' ') || s.length() == 0 ){
                int pre = 0;
                switch (sign){
                    case '+':
                        stack.push(num);break;
                    case '-':
                        stack.push(-num);break;
                    //只需要拿出前一个数字做对应的运算即可
                    case '*':
                        pre = stack.peek();stack.pop();
                        stack.push(pre*num);
                        break;
                    case '/':
                        pre = stack.peek();stack.pop();
                        stack.push(pre/num);
                        break;
                }
                //更新符号为当前符号,数字清零
                sign = c;
                num=0;
            }
            if(c == ')'){
                break;
            }
        }
        //将栈中的所有结果进行求和
        int res = 0;
        while (!stack.isEmpty()){
            res += stack.peek();
            stack.pop();
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

• 这里稍微理解一下两个条件

            if(c == '('){
                num = helper(s);
            }
			if(c == ')'){
                break;
            }
1
2
3
4
5
6

• 这两个条件显然是递归的开始条件和结束条件，但是如何理解其在代码结构中的位置?
• 也就是说为什么(需要放在switch之前?)为什么要放在switch之后?
• [1] 这是因为当遇到(的时候，我们是将(作为一个数字来看待的，而数字是需要进入switch进行处理的，因此需要放在switch之前
• [2] 而遇到 )的时候，仅根据(!Character.isDigit(c) && c!=' ')是可以直接在switch之前接上这个条件，但是要注意，当输入的表达式字符串其最后一个字符是)的时候，直接break掉了，导致之前处理得到的num没有进入stack就会导致漏数。