Poison

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
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
class Solution {
    public int calculate(String s) {
        s = s.replaceAll(" ", "");

        // 思路：将所有的计算符按照二元计算符处理
        Stack<Character> operatorStack = new Stack<>();
        Stack<Integer> numStack = new Stack<>();
        numStack.push(0); // 放入 0 是为了处理纯负数的情况，如表达式 '-5', 此时等同于表达式 '0-5'

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                operatorStack.push(c);
            } else if (c == ')') {
                while (!operatorStack.isEmpty()) {
                    if (operatorStack.peek() == '(') {
                        operatorStack.pop();
                        break;
                    } else {
                        calc(operatorStack, numStack);
                    }
                }
            } else 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.charAt(i) is not digit
                i--;
                numStack.push(num);
            } else {
                // 处理 "1-(-2)" 类似的情况，此时需要在括号出现后补 0, 因为所有的计算符都作为二元计算符处理
                if (i > 0 && s.charAt(i - 1) == '(') {
                    numStack.push(0);
                }

                while (!operatorStack.isEmpty() && !(operatorStack.peek() == '(')) {
                    calc(operatorStack, numStack);
                }
                operatorStack.push(c); // 不要忘记将操作符入栈
            }
        }

        while (!operatorStack.isEmpty()) {
            calc(operatorStack, numStack);
        }

        return numStack.pop();
    }

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

224. Basic Calculator