LeetCode 224 基本计算器

Ciel Yang 收录于类别练习 OJ解题报告

2021-03-10 2021-03-10 约 5043 字预计阅读 11 分钟

本题是一道经典的栈练习题，能很好的考察对栈性质的掌握，同时解法众多，值得细究。

题目描述

原题链接如下： LeetCode 224 基本计算器

题目大意

假设 s 是一个加减法表达式，且可能含有括号和空格，要求计算表达式的值。

输入与输出

示例输入为：

1
2
3
4
5
6
7
8
Input 1:
s = "1 + 1"

Input 2:
s = " 2-1 + 2 "

Input 3:
s = "(1+(4+5+2)-3)+(6+8)"

s 的长度范围区间为 $[1, 300000]$
s 只包含
- 数字
- $+$
- $-$
- $($
- $)$
- 空格
s 一定是一个有效的表达式

对应输出为：

1
2
3
4
5
6
7
8
Output 1:
2

Output 2:
3

Output 3:
23

解题思路

本题的基本思路非常清晰，就是使用基本的算数规则，先计算括号内部的值然后再逐步向外计算外层表达式的值。不妨从简单情况开始思考，逐步增加问题复杂度。

因为表达式的计算符号只有 $+$ 和 $-$，算术计算的优先级相同，都需要从左向右计算。那么，只要我们从左向右遍历输入数据，会不断遇到 $left \pm right$ 这样的子表达式。如果 left 和 right 只是简单的数字，那么遍历到这样的结构直接进行计算即可，具体如下：

设置初始缓存

使用一个数字（命名为 left）缓存操作符左侧计算结果，初始为 0
使用另一个数字（命名为 right）缓存字符到整数的中间数据，也是操作符右侧的数字，初始为 0
使用一个字符（命名为 op）缓存操作符，初始为 $+$ 方便处理输入数据头部的正负符号

逐个字符遍历输入数据，根据每个字符 c 的不同情况分别处理：

如果遇到数字字符，则使用简单计算加入缓存 right 之中：right = right * 10 + (c - '0')
如果遇到 $+$ 或 $-$，则直接计算缓存的操作符的计算结果，并更新为 left 的值，并把 right 置为 0
- op 为 $+$ 时，结果是 $left + right$
- op 为 $-$ 时，结果是 $left - right$

最后再使用 op 计算 $left \pm right$ 的值就是最终结果。

这样，我们就保证了在遇到第二个操作符的时候，先计算第一个操作符对应的结果，那么也就保证了计算顺序的正确。而本身这个初始值的设置对答案也无影响，相当于把表达式变成了 $0 + s$，单纯的方便理解和循环计算。

但是，本题还可能有括号出现，left 和 right 其实是个组成规则和 s 一样的子表达式。此时，我们其实仍使用同样的思路，一样需要缓存 left 或者其结果，并缓存操作符，然后计算 right 的结果。最后，结合 right 和 left 的计算结果，计算总体的表达式值。显然，这个表达式是个递归的结构，需要不断递归计算 left 和 right，所有有了多种不同的解法：

如果直接使用暴力递归解题，需要从外向内剥除括号不断进入新一层的递归计算子表达式，最后统合子式结果计算总体结果
如果使用迭代替换递归，则需要不断缓存外侧数据，由内而外计算子表达式，显然需要使用栈
本题亦可使用词法分析方式，使用简单的操作函数对应不同的字符类型，实现一个极其简单的算式编译器

注意：
因为一般的程序语言需要注意保持容器内部的数据类型一致，但是我们需要同时缓存数据和对应的操作符，所以还有双栈解法和单栈解法的区别
一般情况下，无需关心空格元素，遍历字符时跳过即可

递归解法：

简而言之，本题的递归的核心思路就是先计算括号内的子表达式，然后使用这个值代替原来的括号包裹的子表达式。

显然，递归的框架是 DFS。我们从左向右扫描输入数据，如果没有遇到括号就不断按照上面已经列出的步骤计算结果。一旦遇到 $($ 时就意味着进入下一层递归程序，这样保证每层的递归程序需要处理的就是一个简单的表达式，而直到遇到 $)$ 就意味着一定匹配本层递归的入口 $($，即需要结束本层递归计算返回结果，此时下一层递归返回的子表达式的值就相当于简单表达式中解析完了一个数字。

另外，在下一层递归结束时，我们需要返回上一层程序以继续正常的计算步骤。但是，此时如果没有额外的干预，上一层的程序仍停留在下一层的递归入口处以接收返回值。而子表达式的结尾一定在递归入口右侧，所以我们需要知道子表达式的结尾在何处，以便在深层递归结束之后完成后，让上一层的程序从子表达式的结尾处继续计算。那么，我们就需要一个在所有递归结构之外的变量储存计算进度，可以是类的私有域或者全局变量。（当然，某些语言也可以使用指针或传递引用解决此问题，或者把原始数据放入字符队列中进行遍历。）

递归解法实际上顺序扫描了每个字符，故时间复杂度是 $O(n)$。

双栈解法一：

因为迭代解法需要缓存数字和操作符，我们可以使用两个栈分别存储两种数据，实际是根据无括号的计算程序修改而来。如果要处理无括号的表达式，我们需要根据遍历遇到的元素进行分类操作：

遇到数字就把它缓存到数字栈中
遇到 $+$ 或 $-$ 时，为了保证表达式计算顺序正确，要检查操作符栈是否已缓存操作符：
- 如果已缓存操作符，需要先计算已经缓存的操作结果，不断弹出操作符和两个数字，此时数字栈中必然有数字，但需要检查可弹出的数字个数：
  - 如果有两个数字则正常计算
  - 如果只能弹出一个数字，则说明这是开始的数字，操作符是开始数字的正负符号
- 如果没有缓存操作符，则直接把操作符存入操作符栈

直到所有字符遍历完成后，可能操作符栈仍然非空，但是也最多只有一个操作符，则需要根据此操作符进行相应计算（仍要注意数字栈中是否只有一个数字），得到最后结果。

那么，如果有括号的情况也就非常简单，只需要添加一些额外的细节：

遇到 $($ 时，把它存入符号栈，作为终止符
遇到 $+$ 或 $-$ 操作符时，仍需要不断弹出操作符和数字进行计算，直到遇到 $($ 则终止弹出
遇到 $)$ 和遇到 $+$ 或 $-$ 操作符时操作类似，只是需要在最后弹出和它匹配的 $($，当然也就是此时栈顶的操作符

此解法看似有多个循环，需要不断弹出已经扫描过的操作符回头进行计算，其实我们每个操作符只会计算一次，同一层括号内的操作符其实只会缓存一个，之前的都会弹出计算，所以时间复杂度仍然是 $O(n)$。只不过，数字栈的出入栈太频繁，实际运行时容器的操作会比较费时，故实际的时间复杂度不会太好。

双栈解法二：

第一种双栈解法的数字栈操作稍显复杂，其实我们最后分析数字栈中不会缓存太多数字，同一层的 $+$ 和 $-$ 都已经不断计算完毕了，只会因为不断遇到括号才不断缓存外层括号的计算结果，即只有碰到括号才入栈。其实第一种双栈解法更适合处理多种操作符、多种计算优先级的情况，毕竟我们是遇到第二个操作符的时候才计算第一个操作符的处理结果，多优先级情况下可能需要先计算第二个操作符的计算。如果输入数据无括号，那么本解法不会有多少变化。

参照双栈解法一，如果输入数据加入括号，那么：

遇到 $($ 时意味着我们要开始计算括号内的子表达式，此时参考程序的初始缓存设置：
1. 把括号外层的计算结果 left 和括号之前的操作符分别存入各自的栈中
2. 将 left 和 right 置为 0
3. 把 op 置为 $+$
遇到 $)$ 时：
1. 结合 op 以及 left 和 right 计算结果赋值给 right
2. left 再赋值为数字栈顶的数字，并把它出栈
3. op 赋值为操作栈顶的操作符，并把它出栈

这样我们就能够保证无括号操作的缓存约束始终不变，那就无需再改变其他的操作。

理论上，这个解法的时间复杂度不会更优秀，但是减少了很多容器操作，实际的运行时间要减少很多。

单栈解法一：

再进一步思考，我们的表达式只有加减法两种计算，而减法实际上就是加一个负数，所以只要我们能正确处理减号和括号嵌套之后的数字符号问题，我们所有的计算都能转化为加法。而一旦此思路可行，我们所有的操作符都是一样的，那么也就无需缓存操作符，直接默认使用加法即可。实际上这样的转化并不复杂，我们注意到 $\pm a$ 可以转化为 $\pm 1 \times a$，这样我们所有的简单算式 $a \pm b$ 就可以转化为 $a + \pm{1} \times b$。也就是说我们我们原来的操作符只需要变为 1 或 -1 即可，而一旦操作符能够如此转化，那么我们也就无需额外使用一个操作符栈。毕竟，我们再双栈解法二中的栈中缓存数据只保存括号外的操作符，和这个操作符的左边表达式的计算结果，两个栈的元素数量是相等的。

我们可以根据双栈解法二的思路稍加调整即可得到新的单栈解法：

修改初始缓存如下：
- left 和 right 的设置不变
- 使用 sign 缓存代表的操作符，初始为 1
遍历时的各种操作调整如下：
- 遇到数字字符的操作不变
- 遇到 $+$ 和 $-$ 时：
  1. 计算操作都是 $left + sign \times right$
  2. 遇到 $+$ 时 sign 为 1，否则为 -1
  3. right 仍同样置为 0
- 遇到 $($ 时，一样要参考初始的缓存设置：
  1. 先后把 left 和 sign 入栈
  2. left 和 right 同样置为 0
  3. sign 置为 1
- 遇到 $)$ 时：
  1. right 赋值为 $left + sign \times right$
  2. 弹出栈顶，赋值给 sign
  3. 弹出栈顶，赋值给 left

最后的答案就是 $left + sign \times right$。

单栈解法二：

我们还可以注意到本题因为运算符只涉及 $+$ 和 $-$，可以用来剥除括号，而实际上本题最麻烦的地方也就是剔除括号的影响。假设 $a \pm b$ 中 b 是一个带有括号的表达式，那么去除 b 的最外层括号的操作非常简单，只需要对前面的操作符分情况讨论即可：

如果是 $+$，那么去除括号之后没有任何影响
如果是 $-$，那么去除括号之后只需要把 b 中原来的 $+$ 变为 $-$，把 $-$ 变为 $+$

即如果只要除去一层括号，那么我们只需要缓存括号外左侧的操作符即可。在去除括号之后缓存的操作符就不再有用，即遇到 $)$ 后就无需在意它了。而如果 b 的内部仍有括号需要去除，比如 b 是 $(c - (d + e) - f)$，则只需要再缓存一个括号外层的操作符（此例为 $-$），而它本身就受到之前缓存的操作符的影响，综合这两者再对 b 内部的括号进行剥除。而一旦 b 内部括号剥除完毕，则第二个缓存就无用了，之后的计算只需考虑第一个操作符的影响。综上所述，我们可以看出只要我们一遇到 $($ 就缓存它左侧的操作符，而每次遇到 $)$ 去除最近缓存的操作符，我们就能正确地计算剥除所有括号之后所有的操作符应该转化为什么样子。显然，这个缓存结果是栈。这样，我们就能够结合无括号表达式的计算得到最终结果。

语义分析解法：

当然，本题显然可以使用我们再编译语言中学过的语义分析方法得出语法，然后照着语法实现代码即可。本题的语法如下：

$$ \begin{aligned} expr =& term\ { (+|-)\ term }\\ term =& [+|-]\ (Int\ |\ ‘(’ expr ‘)’)\\ \end{aligned} $$

上述解法和我们再一些例题中看到的公式有些许区别，主要是因为本题没有乘除法，而 $term$ 如此复杂是因为要处理如下特别的输入：

$-(1 - (2 - 3)) + 4$
$-1 + 2 - 3$

另外，因为题目确定输入数据必定合法，所以本解法的实际代码可以写得比较简陋，省略了常见的 match(c: Char) 方法。另外，实际上如果严格按照规定，负数或者有前置负号的子表达式需要额外的判断，此题输入简单所以也一并省略了。

代码

递归解法：

 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 {
    private var idx = 0
    fun calculate(s: String): Int {
        return dfs(s)
    }

    private fun dfs(s: String): Int {
        var left = 0
        var right = 0
        var op = '+'
        loop@ while (idx < s.length) {
            when (s[idx]) {
                ' ' -> idx++
                in '0'..'9' -> {
                    right = 0
                    while (idx < s.length && s[idx].isDigit()) {
                        right = right * 10 + (s[idx++] - '0')
                    }
                }
                '+', '-' -> {
                    left = if (op == '+') left + right else left - right
                    op = s[idx++]
                }
                '(' -> {
                    idx++
                    right = dfs(s)
                }
                ')' -> {
                    idx++
                    break@loop
                }
            }
        }
        return if (op == '+') left + right else left - right
    }
}

双栈解法一：

 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
class Solution {
    fun calculate(s: String): Int {
        val numStack = ArrayDeque<Int>()
        val opStack = ArrayDeque<Char>()
        var i = 0
        while (i < s.length) {
            when (s[i]) {
                '(' -> opStack.addLast(s[i++])
                '+', '-', ')' -> {
                    while (opStack.isNotEmpty() && opStack.last() != '(') {
                        val right = numStack.removeLast()
                        val left = if (numStack.isNotEmpty()) numStack.removeLast() else 0
                        val t = if (opStack.removeLast() == '+') left + right else left - right
                        numStack.addLast(t)
                    }
                    if (s[i] != ')') opStack.addLast(s[i])
                    else opStack.removeLast()
                    i++
                }
                in '0'..'9' -> {
                    var right = 0
                    while (i < s.length && s[i].isDigit()) {
                        right = right * 10 + (s[i++] - '0')
                    }
                    numStack.addLast(right)
                }
                else -> i++
            }
        }
        if (opStack.isNotEmpty()) {
            val right = numStack.removeLast()
            val left = if (numStack.isNotEmpty()) numStack.removeLast() else 0
            val t = if (opStack.removeLast() == '+') left + right else left - right
            numStack.addLast(t)
        }
        return numStack.last()
    }
}

双栈解法二：

 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
class Solution {
    fun calculate(s: String): Int {
        var left = 0
        val opStack = ArrayDeque<Char>()
        val numStack = ArrayDeque<Int>()
        var right = 0
        var op = '+'
        for (c in s) {
            when (c) {
                '+', '-' -> {
                    left = if (op == '+') left + right else left - right
                    right = 0
                    op = c
                }
                '(' -> {
                    numStack.addLast(left)
                    opStack.addLast(op)
                    op = '+'
                    right = 0
                    left = 0
                }
                ')' -> {
                    right = if (op == '+') left + right else left - right
                    left = numStack.removeLast()
                    op = opStack.removeLast()
                }
                in '0'..'9' -> right = right * 10 + (c - '0')
            }
        }
        left = if (op == '+') left + right else left - right
        return left
    }
}

单栈解法一：

 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
class Solution {
    fun calculate(s: String): Int {
        var left = 0
        var sign = 1
        val stack = ArrayDeque<Int>()
        var right = 0
        for (c in s) {
            when (c) {
                '+', '-' -> {
                    left += sign * right
                    sign = if (c == '+') 1 else -1
                    right = 0
                }
                '(' -> {
                    stack.addLast(left)
                    stack.addLast(sign)
                    left = 0
                    right = 0
                    sign = 1
                }
                ')' -> {
                    right = left + sign * right
                    sign = stack.removeLast()
                    left = stack.removeLast()
                }
                in '0'..'9' -> right = right * 10 + (c - '0')
            }
        }
        return left + sign * right
    }
}

单栈解法二：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    fun calculate(s: String): Int {
        var left = 0
        val stack = ArrayDeque<Int>()
        stack.addLast(1)
        var sign = 1
        var right = 0
        for (c in s) {
            when (c) {
                '+', '-' -> {
                    left += sign * right
                    right = 0
                    sign = if (c == '+') stack.last() else -stack.last()
                }
                '(' -> stack.addLast(sign)
                ')' -> stack.removeLast()
                in '0'..'9' -> {
                    right = right * 10 + (c - '0')
                }
            }
        }
        return left + sign * right
    }
}

类词法分析解法：

 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
class Solution {
    private var idx = -1
    private lateinit var s: String
    private var token = ' '
    private lateinit var tokenType: TokenType

    fun calculate(s: String): Int {
        idx = -1
        this.s = s
        nextToken()
        return expr()
    }

    private fun expr(): Int {
        var left = term()
        while (tokenType == TokenType.OP) {
            val sign = if (token == '+') 1 else -1
            nextToken()
            val right = term()
            left += sign * right
        }
        return left
    }

    private fun term(): Int {
        var sign = 1
        if (tokenType == TokenType.OP) {
            if (token == '-') sign = -1
            nextToken()
        }
        val re: Int
        if (tokenType == TokenType.LP) {
            nextToken()
            re = expr()
            nextToken() // skip ')'
        } else {
            re = number()
        }
        return sign * re
    }

    private fun number(): Int {
        var re = 0
        while (tokenType == TokenType.INT) {
            re = re * 10 + (token - '0')
            nextToken()
        }
        return re
    }

    private fun nextToken() {
        idx++
        while (idx < s.length && s[idx].isWhitespace()) idx++
        if (idx == s.length) {
            tokenType = TokenType.END
            return
        }
        token = s[idx]
        tokenType = when (token) {
            '+', '-' -> TokenType.OP
            '(' -> TokenType.LP
            ')' -> TokenType.RP
            else -> TokenType.INT
        }
    }
}

enum class TokenType {
    OP, INT, LP, RP, END
}

目录

LeetCode 224 基本计算器

题目描述

题目大意

输入与输出

解题思路

递归解法：

双栈解法一：

双栈解法二：

单栈解法一：

单栈解法二：

语义分析解法：

代码