224. 基本计算器

1. 题目

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

1
2
输入：s = "1 + 1"
输出：2

示例 2：

1
2
输入：s = " 2-1 + 2 "
输出：3

示例 3：

1
2
输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23

提示：

  • 1 <= s.length <= 3 * 10^5
  • s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
  • s 表示一个有效的表达式
  • ‘+’ 不能用作一元运算(例如， “+1” 和 "+(2 + 3)" 无效)
  • ‘-‘ 可以用作一元运算(即 “-1” 和 "-(2 + 3)" 是有效的)
  • 输入中不存在两个连续的操作符
  • 每个数字和运行的计算将适合于一个有符号的 32位 整数

2. 思路

  • 本题需要将中缀表达式进行结果的计算，同时已知题目只包含+和-运算符

  • 整体思路是将中缀表达式转化为逆波兰表达式，随后再使用栈对逆波兰表达式进行值的计算，可参考150. 逆波兰表达式求值

  • 对中缀表达式进行转化前，需要进行以下处理，以保证转逆波兰式的正确性：

    • 剔除处理字符串中已有的空格
    • 如果首个字符为-符号时，需要在字符串前加入0便于后续转化计算（比如-2+1同义为0-2+1）
    • 对1+(-1+1)同义为1+(0-1+1)以便于后续转化计算

  • 初始化为逆波兰式需要用到两个常量级存储空间，一个操作符栈opsStack用于记载操作符顺序，以及一个操作数列表tokens

  • 遍历中缀表达式中的字符：

    • 当遇到字符为(时，直接写入操作符栈
    • 当遇到字符为)时，将栈中的所有操作符依次出栈写入操作数列表中形成后缀表达式，直至栈顶元素为(，随后将栈顶元素为(的元素进行出栈
    • 当遇到字符为+时，判断栈顶是否存在其他操作符(比如+或-)，如果有，则先对其前置的所有操作符进行出栈写入到操作数列表中形成后缀表达式，随后在讲当前字符+写入操作符栈中
    • 当遇到字符为-时，同上所示
    • 当遇到的字符为数字时，为了防止出现多位数值的情况，将持续找到所有的连续数字，并将该数字串作为一个数值写入操作数栈中

  • 完成以上遍历后即可得到后缀表达式，即逆波兰表达式，随后利用一个栈得到逆波兰表达式的计算结果作为返回值

3. 代码

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
73
74
75
76
77
78
class Solution {
    public int calculate(String s) {
        s = s.replace(" ", "");
        s = s.replace("(-", "(0-");
        if (s.charAt(0) == '-') {
            s = "0" + s;
        }
        var opsStack = new ArrayDeque<Character>();
        var tokens = new ArrayList<String>();
        var arr = s.toCharArray();

        var i = 0;
        while (i < arr.length) {
            var ch = arr[i];
            if (isOperator(ch)) {
                while (!opsStack.isEmpty() && opsStack.peek() != '(') {
                    tokens.add(opsStack.pop() + "");
                }
                opsStack.push(ch);
            } else if (ch == '(') {
                opsStack.push(ch);
            } else if (ch == ')') {
                while (opsStack.peek() != '(') {
                    tokens.add(opsStack.pop() + "");
                }
                opsStack.pop();
            } else {
                var val = getValue(arr, i);
                tokens.add(val);
                i += (val.length() - 1);
            }
            i++;
        }

        while (!opsStack.isEmpty()) {
            tokens.add(opsStack.pop() + "");
        }

        return count(tokens);
    }

    private boolean isOperator(char c) {
        return c == '+' || c == '-';
    }

    private int count(ArrayList<String> tokens) {
        var stack = new ArrayDeque<Integer>();

        for (var token : tokens) {
            if ("-".equals(token)) {
                var secondVal = stack.pop();
                var firstVal = stack.pop();
                stack.push(firstVal - secondVal);
            } else if ("+".equals(token)) {
                stack.push(stack.pop() + stack.pop());
            } else {
                stack.push(Integer.valueOf(token));
            }
        }

        return stack.pop();
    }

    private String getValue(char[] arr, int startIndex) {
        var val = new StringBuilder();

        for (var i = startIndex; i < arr.length; ++i) {
            var ch = arr[i];
            if (Character.isDigit(ch)) {
                val.append(ch);
            } else {
                break;
            }
        }

        return val.toString();
    }
}

4. 复杂度

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

image-20230913231837172