---

0224. 基本计算器

• 标签：栈、递归、数学、字符串
• 难度：困难

题目链接

• 0224. 基本计算器 - 力扣

题目大意

描述：

给定一个字符串表达式 $s$。

要求：

实现一个基本计算器来计算并返回它的值。

说明：

• 注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval()。
• $1 \le s.length \le 3 \times 10^{5}$。
• $s$ 由数字、'+'、'-'、'('、')'、和 ' ' 组成。
• $s$ 表示一个有效的表达式。
• '+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)。
• '-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)。
• 输入中不存在两个连续的操作符。
• 每个数字和运行的计算将适合于一个有符号的 32 位整数。

示例：

• 示例 1：

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

• 示例 2：

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

解题思路

思路 1：栈 + 递归

使用栈来处理括号和运算符的优先级。由于只有加法和减法，我们可以通过维护一个符号栈来处理括号内的运算。

具体步骤如下：

1. 使用栈 $stack$ 来存储当前的计算结果和符号。
2. 使用变量 $result$ 来存储当前的计算结果。
3. 使用变量 $sign$ 来存储当前的符号（$+1$ 或 $-1$）。
4. 遍历字符串 $s$：
   • 如果遇到数字，则计算完整的数字值。
   • 如果遇到 +，则设置 $sign = 1$。
   • 如果遇到 -，则设置 $sign = -1$。
   • 如果遇到 (，则将当前的 $result$ 和 $sign$ 压入栈中，并重置 $result$ 和 $sign$。
   • 如果遇到 )，则从栈中弹出之前的结果和符号，与当前结果进行运算
5. 最后返回 $result$。

这种方法可以正确处理括号的嵌套和运算符的优先级。

思路 1：代码

class Solution:
    def calculate(self, s: str) -> int:
        # 使用栈来处理括号和运算符
        stack = []
        result = 0  # 当前计算结果
        sign = 1    # 当前符号，1 表示正数，-1 表示负数
        
        i = 0
        while i < len(s):
            char = s[i]
            
            if char.isdigit():
                # 计算完整的数字
                num = 0
                while i < len(s) and s[i].isdigit():
                    num = num * 10 + int(s[i])
                    i += 1
                i -= 1  # 回退一位，因为外层循环会 i += 1
                result += sign * num
                
            elif char == '+':
                sign = 1
                
            elif char == '-':
                sign = -1
                
            elif char == '(':
                # 遇到左括号，将当前结果和符号压入栈
                stack.append(result)
                stack.append(sign)
                # 重置结果和符号
                result = 0
                sign = 1
                
            elif char == ')':
                # 遇到右括号，从栈中弹出之前的结果和符号
                result *= stack.pop()  # 弹出符号
                result += stack.pop()  # 弹出之前的结果
                
            # 跳过空格
            i += 1
            
        return result

思路 1：复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是字符串 $s$ 的长度。需要遍历字符串一次。
• 空间复杂度：$O(n)$，最坏情况下栈的深度为 $O(n)$，例如当所有括号都嵌套时。