题目

标题和出处

标题：基本计算器 II

出处：227. 基本计算器 II

难度

7 级

题目描述

要求

给你一个字符串表达式 $\text{s}$，计算并返回它的值。

整数除法应向零取整。

你可以假设给定的表达式总是有效的。所有的中间结果都在范围 ${\text{[-2}}^{\text{31}}{\text{, 2}}^{\text{31}}-\text{1]}$ 内。

注意：你不允许使用任何内置库函数计算数学表达式，例如 $\text{eval()}$。

示例

示例 1：

输入：$\text{s = "3+2*2"}$
输出：$\text{7}$

示例 2：

输入：$\text{s = " 3/2 "}$
输出：$\text{1}$

示例 3：

输入：$\text{s = " 3+5 / 2 "}$
输出：$\text{5}$

数据范围

• $\text{1}\le \text{s.length}\le \text{3}\times {\text{10}}^{\text{5}}$
• $\text{s}$ 由整数和运算符（$\text{‘+’, ‘-’, ‘*’, ‘/’}$）组成，中间由一些空格隔开
• $\text{s}$ 表示一个有效表达式
• 表达式中的所有整数都是非负整数，且在范围 ${\text{[0, 2}}^{\text{31}}-\text{1]}$ 内
• 题目数据保证答案是一个 $\text{32}$ 位整数

解法

思路和算法

计算数学表达式的值，可以使用栈。这道题的数学表达式包含数字、加减号和乘除号，可行的方法有以下两种：

1. 将数学表达式转成逆波兰表达式，然后利用「逆波兰表达式求值」的解法计算数学表达式的值；

2. 先处理乘法和除法运算，后处理加法和减法运算，即可计算数学表达式的值。

上述方法有不同的适用场景。第 1 种方法可以处理的数学表达式的范围较广，四则运算和括号的情况都可以处理，但是需要做两步操作，逻辑较为复杂。第 2 种方法可以处理的数学表达式有局限性，但是逻辑较为简单。

此处提供的解法是上述第 2 种方法。使用两个栈分别存储数字和运算符，遍历数学表达式的过程中维护两个栈的元素并进行相应的计算。

由于给定的数学表达式是有效的表达式，因此不需要做容错处理。从左到右遍历数学表达式，遇到空格则跳过，遇到数字和运算符则做相应的处理。具体做法如下：

• 遇到数字，则将当前数字遍历完毕，然后将当前数字入数字栈；

• 遇到运算符，则需要做以下两步操作：

  1. 检查运算符栈是否为空以及运算符栈的栈顶运算符优先级是否大于或等于当前运算符优先级，如果成立则将数字栈的两个数字出栈以及将运算符栈的一个运算符出栈，执行运算并将运算结果入数字栈，重复该操作直到运算符栈变为空或者运算符栈的栈顶运算符优先级小于当前运算符优先级；

  2. 将当前运算符入运算符栈。

遍历完数学表达式之后，可能两个栈内仍然有元素，因此需要对两个栈内的剩余元素继续计算，最后数字栈内只剩下一个元素，该元素即为数学表达式的值。

上述过程中，为了确保同级运算符的运算顺序为从左到右依次运算，每次遇到运算符时都会首先检查运算符栈的栈顶运算符，如果栈顶运算符的优先级大于或等于当前运算符优先级即执行运算，直到运算符栈变为空或者运算符栈的栈顶运算符优先级小于当前运算符优先级，因此可以确保运算符栈从栈底到栈顶的运算符为严格按照优先级单调递增的顺序，运算符栈内不可能出现连续两个优先级相同的运算符。

考虑以下例子：$s=\text{“5+4*8/10–2*2"}$。数学表达式的计算过程如下。

1. 遇到数字 $5$，将 $5$ 入数字栈。数字栈为 $[5]$，运算符栈为 $[]$，其中左边为栈底，右边为栈顶。

2. 遇到加号，由于运算符栈为空，因此直接将加号入运算符栈。数字栈为 $[5]$，运算符栈为 $[\text{‘+’}]$。

3. 遇到数字 $4$，将 $4$ 入数字栈。数字栈为 $[5,4]$，运算符栈为 $[\text{‘+’}]$。

4. 遇到乘号，由于运算符栈的栈顶是加号，加号优先级低于乘号优先级，因此直接将乘号入运算符栈。数字栈为 $[5,4]$，运算符栈为 $[\text{‘+’},\text{‘*’}]$。

5. 遇到数字 $8$，将 $8$ 入数字栈。数字栈为 $[5,4,8]$，运算符栈为 $[\text{‘+’},\text{‘*’}]$。

6. 遇到除号，执行以下操作。

   1. 由于运算符栈的栈顶是乘号，乘号优先级等于除号优先级，因此将 $8$ 和 $4$ 出数字栈，将乘号出运算符栈，将 $4\ast 8=32$ 入数字栈。数字栈为 $[5,32]$，运算符栈为 $[\text{‘+’}]$。

   2. 将除号入运算符栈。数字栈为 $[5,32]$，运算符栈为 $[\text{‘+’},\text{‘/’}]$。

7. 遇到数字 $10$，将 $10$ 入数字栈。数字栈为 $[5,32,10]$，运算符栈为 $[\text{‘+’},\text{‘/’}]$。

8. 遇到减号，执行以下操作。

   1. 由于运算符栈的栈顶是除号，除号优先级大于减号优先级，因此将 $10$ 和 $32$ 出数字栈，将除号出运算符栈，将 $32/10=3$（注意除法向零取整）入数字栈。数字栈为 $[5,3]$，运算符栈为 $[\text{‘+’}]$。

   2. 由于运算符栈的栈顶是加号，加号优先级等于减号优先级，因此将 $3$ 和 $5$ 出数字栈，将加号出运算符栈，将 $5+3=8$ 入数字栈。数字栈为 $[8]$，运算符栈为 $[]$。

   3. 将减号入运算符栈。数字栈为 $[8]$，运算符栈为 $[\text{‘–’}]$。

9. 遇到数字 $2$，将 $2$ 入数字栈。数字栈为 $[8,2]$，运算符栈为 $[\text{‘–’}]$。

10. 遇到乘号，由于运算符栈的栈顶是减号，减号优先级低于乘号优先级，因此直接将乘号入运算符栈。数字栈为 $[8,2]$，运算符栈为 $[\text{‘–’},\text{‘*’}]$。

11. 遇到数字 $2$，将 $2$ 入数字栈。数字栈为 $[8,2,2]$，运算符栈为 $[\text{‘–’},\text{‘*’}]$。

12. 遍历结束，由于两个栈内还有元素，因此继续运算。将 $2$ 和 $2$ 出数字栈，将乘号出运算符栈，将 $2\ast 2=4$ 入数字栈。数字栈为 $[8,4]$，运算符栈为 $[\text{‘–’}]$。

13. 将 $4$ 和 $8$ 出数字栈，将减号出运算符栈，将 $8-4=4$ 入数字栈。数字栈为 $[4]$，运算符栈为 $[]$。

14. 数字栈内只剩下一个元素 $4$，数学表达式的值为 $4$。

代码

class Solution {
    public int calculate(String s) {
        Deque<Integer> numStack = new ArrayDeque<Integer>();
        Deque<Character> opStack = new ArrayDeque<Character>();
        int length = s.length();
        int index = 0;
        while (index < length) {
            char c = s.charAt(index);
            if (c == ' ') {
                index++;
                continue;
            } else if (Character.isDigit(c)) {
                int num = 0;
                while (index < length && Character.isDigit(s.charAt(index))) {
                    num = num * 10 + s.charAt(index) - '0';
                    index++;
                }
                numStack.push(num);
            } else {
                int currPrecedence = getPrecedence(c);
                while (!opStack.isEmpty()) {
                    int prevPrecedence = getPrecedence(opStack.peek());
                    if (prevPrecedence >= currPrecedence) {
                        calculate(numStack, opStack);
                    } else {
                        break;
                    }
                }
                opStack.push(c);
                index++;
            }
        }
        while (!opStack.isEmpty()) {
            calculate(numStack, opStack);
        }
        return numStack.pop();
    }

    public void calculate(Deque<Integer> numStack, Deque<Character> opStack) {
        if (!opStack.isEmpty()) {
            char op = opStack.pop();
            int num2 = numStack.pop();
            int num1 = numStack.pop();
            switch (op) {
            case '+':
                numStack.push(num1 + num2);
                break;
            case '-':
                numStack.push(num1 - num2);
                break;
            case '*':
                numStack.push(num1 * num2);
                break;
            case '/':
                numStack.push(num1 / num2);
                break;
            default:
            }
        }
    }

    public int getPrecedence(char op) {
        if (op == '*' || op == '/') {
            return 2;
        } else {
            return 1;
        }
    }
}
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

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是字符串 $s$ 的长度。需要遍历字符串 $s$ 一次，每个字符的操作时间都是 $O(1)$。

• 空间复杂度：$O(n)$，其中 $n$ 是字符串 $s$ 的长度。空间复杂度主要取决于栈空间，栈内元素个数不会超过 $n$。