224. Basic Calculator

Stack

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
class Solution {
    public int calculate(String s) {
        int ans = 0, sign = 1; // sign 表示当前数字前的符号
        Stack<Integer> signStack = new Stack<>(); // 括号外层的符号
        signStack.push(1);

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ' ') {
                continue;
            } else if (c == '(') {
                signStack.push(signStack.peek() * sign);
                sign = 1;
            } else if (c == ')') {
                signStack.pop();
            } else if (c == '+') {
                sign = 1;
            } else if (c == '-') {
                sign = -1;
            } else {
                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--;
                ans += signStack.peek() * sign * num;
            }
        }

        return ans;
    }
}

Stack

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
class Solution {
    public int calculate(String s) {
        Stack<Integer> levelSignStack = new Stack<>(); // 栈顶为当前层括号外侧实际的符号
        levelSignStack.push(1); // 最外层的数字统一视为在一对括号内，此时括号外为正号
        int sign = 1; // 同上，该变量表示表达式全部展开后当前数字前的符号

        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ' ') {
                continue;
            } else if (c == '(') {
                levelSignStack.push(sign);
            } else if (c == ')') {
                levelSignStack.pop();
            } else if (c == '+') {
                sign = levelSignStack.peek(); // 同括号外侧实际符号
            } else if (c == '-') {
                sign = -levelSignStack.peek(); // 与括号外侧实际符号相反
            } else {
                // c is digit
                int num = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    int x = s.charAt(i) - '0';
                    num = num * 10 + sign * x;
                    i++;
                }
                i--;
                
                result += num;
            }
        }

        return result;
    }
}

Stack

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
class Solution {
    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 (c == '(') {
                operatorStack.push(c);
            } else if (c == ')') {
                // (1+2), 因为没有遇到第二个操作符，所以需要在此处触发计算
                while (operatorStack.peek() != '(') {
                    calc(operatorStack, numStack);
                }
                operatorStack.pop();
            } else if (c == '+' || c == '-') {
                // 补 0，将 -1 转换为 0-1 这样的二元运算表达式
                if (c == '-' && (i == 0 || s.charAt(i - 1) == '(')) {
                    numStack.push(0);
                }
                while (!operatorStack.isEmpty() && operatorStack.peek() != '(') {
                    calc(operatorStack, numStack);
                }
                operatorStack.push(c);
            } else {
                int num = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + (s.charAt(i++) - '0');
                }
                i--;
                numStack.push(num);
            }
        }

        // 1+2, 因为没有遇到第二个操作符，所以需要在此处触发计算
        while (!operatorStack.isEmpty()) {
            calc(operatorStack, numStack);
        }

        return numStack.peek();
    }

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

关键点在遇到符号时触发之前表达式的计算，这是最关键的，而不是数字结束时触发计算，可以用表达式 “(7)-(0)+(4)” 来加深理解。

References

224. Basic Calculator