227. Basic Calculator II 

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Solution {
    private static final Map<Character, Integer> OPERATOR_TO_PRECEDENCE_MAP;

    static {
        OPERATOR_TO_PRECEDENCE_MAP = new HashMap<>();
        OPERATOR_TO_PRECEDENCE_MAP.put('-', 0);
        OPERATOR_TO_PRECEDENCE_MAP.put('+', 0);
        OPERATOR_TO_PRECEDENCE_MAP.put('*', 1);
        OPERATOR_TO_PRECEDENCE_MAP.put('/', 1);
    }

    public int calculate(String s) {
        s = s.replaceAll(" ", "");

        // 思路：将所有的操作符按照二元操作符处理
        Stack<Integer> numStack = new Stack<>();
        Stack<Character> operatorStack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int num = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + (s.charAt(i) - '0');
                    i++;
                }
                // i == s.length() or s[i] is not digit
                i--;
                numStack.push(num);
            } else {
                // 补 0，将 -1 转换为 0-1 这样的二元运算表达式
                if (c == '-' && i == 0) {
                    numStack.push(0);
                }

                // 注意此处是 while 而不是 if, 可以用 "1*2-3/4+5*6-7*8+9/10" 进行验证，即保证从左到右计算，若使用 if 会导致乘除法计算的结果全部位于栈中，最后 "2-0+30-56+0" 从右到左计算而得到错误结果。while 的另一层含义为使操作符栈中的操作符优先级递增，以保证最后 while 计算结果正确
                while (!operatorStack.isEmpty() && OPERATOR_TO_PRECEDENCE_MAP.get(operatorStack.peek()) >= OPERATOR_TO_PRECEDENCE_MAP.get(c)) {
                    calc(numStack, operatorStack);
                }
                operatorStack.push(c);
            }
        }

        // 注意此处是 while, 如表达式 '3+2*2', 最后操作符栈中有两个操作符，操作数栈中有三个操作数
        while (!operatorStack.isEmpty()) {
            calc(numStack, operatorStack);
        }

        return numStack.pop();
    }

    private void calc(Stack<Integer> numStack, Stack<Character> operatorStack) {
        int b = numStack.pop(), a = numStack.pop();
        char operator = operatorStack.pop();
        switch (operator) {
            case '+':
                numStack.push(a + b);
                break;
            case '-':
                numStack.push(a - b);
                break;
            case '*':
                numStack.push(a * b);
                break;
            case '/':
                numStack.push(a / b);
                break;
            default:
                throw new IllegalArgumentException("Unsupported operator: " + operator);
        }
    }
}

关键点在遇到符号时触发之前优先级相同或更高的表达式的计算。

References

227. Basic Calculator II
面试题 16.26. 计算器