Adrian Wang's blog

一个完全由AI生成，但是内容高质量的Blog

LeetCode 224 - 基本计算器（Basic Calculator）

Posted on Edited on In , ,
Symbols count in article: 2.7k Reading time ≈ 2 mins.
使用栈解决带括号的基本计算器问题，掌握处理优先级和符号的核心技巧

问题描述

给你一个字符串表达式 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 \leq s.length \leq 3 \times 10^5$
  • s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
  • s 表示一个有效的表达式
  • '+' 不能用作一元运算的正号
  • '-' 可以用作一元运算的负号
  • 输入中不存在两个连续的操作符

解题思路

这道题的核心在于处理带括号的表达式计算。关键难点是：

  1. 符号的传递：括号内的符号需要与括号外的符号相乘
  2. 优先级处理：括号具有最高优先级
  3. 状态保存：进入括号时需要保存当前状态

核心思想

使用栈来处理括号的嵌套：

  • 遇到 (：将当前的结果和符号压入栈中，重新开始计算
  • 遇到 )：从栈中弹出之前的结果和符号，与当前结果合并

算法步骤

  1. 初始化变量：

    • stack：存储历史状态的栈
    • sign：当前数字的符号（1 或 -1）
    • res：当前表达式的计算结果

  2. 遍历字符串：

    • 数字：解析完整数字，加到结果中
    • 符号 +/-：更新下一个数字的符号
    • 左括号 (：保存当前状态到栈，重置计算
    • 右括号 )：恢复之前状态，合并计算结果

  3. 状态转换图：

1
2
3
4
5
6
7
8
9
10
11
12
13
普通计算 ──┐
           │ 遇到 '('
           ↓
       保存状态到栈
           │
           ↓
       重新开始计算
           │ 遇到 ')'
           ↓
       从栈恢复状态
           │
           ↓
       合并计算结果

实现细节

关键点分析

  1. 符号处理：

    • 使用 sign 变量记录当前数字的符号
    • 遇到 + 设置 sign = 1，遇到 - 设置 sign = -1

  2. 括号处理：

    • 左括号：stack.push(sign) → stack.push(res) → 重置状态
    • 右括号：弹出 preRes 和 preSign，计算 preSign * res + preRes

  3. 数字解析：

    • 连续读取数字字符，构建完整的数字
    • 注意处理多位数字的情况

执行过程示例

以 "(1+(4+5+2)-3)+(6+8)" 为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
步骤详解：
1. 遇到 '('：stack = [1, 0], res = 0, sign = 1
2. 数字 1：res = 1
3. 遇到 '+'：sign = 1
4. 遇到 '('：stack = [1, 0, 1, 1], res = 0, sign = 1
5. 数字 4：res = 4
6. 遇到 '+'：sign = 1
7. 数字 5：res = 9
8. 遇到 '+'：sign = 1
9. 数字 2：res = 11
10. 遇到 ')'：preRes = 1, preSign = 1, res = 1 * 11 + 1 = 12
11. 遇到 '-'：sign = -1
12. 数字 3：res = 12 + (-1) * 3 = 9
13. 遇到 ')'：preRes = 0, preSign = 1, res = 1 * 9 + 0 = 9
...

代码实现

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
func calculate(s string) int {
    stack := []int{}      // 存储历史状态的栈
    sign := 1             // 当前数字的符号：1表示正，-1表示负
    res := 0              // 当前表达式的计算结果

    for i := 0; i < len(s); i++ {
        char := s[i]
        
        if unicode.IsDigit(rune(char)) {
            // 解析完整的数字（可能是多位数）
            num := 0
            for i < len(s) && unicode.IsDigit(rune(s[i])) {
                num = num*10 + int(s[i]-'0')
                i++
            }
            i-- // 回退一位，因为外层循环会自动 i++
            
            // 将数字加到当前结果中
            res += sign * num
            
        } else if char == '+' {
            // 下一个数字为正数
            sign = 1
        } else if char == '-' {
            // 下一个数字为负数
            sign = -1
        } else if char == '(' {
            // 遇到左括号：保存当前状态，重新开始计算
            stack = append(stack, sign)  // 保存当前符号
            stack = append(stack, res)   // 保存当前结果
            res = 0                      // 重置结果
            sign = 1                     // 重置符号
        } else if char == ')' {
            // 遇到右括号：恢复之前状态，合并结果
            preRes := stack[len(stack)-1]    // 弹出之前的结果
            stack = stack[:len(stack)-1]
            preSign := stack[len(stack)-1]   // 弹出之前的符号
            stack = stack[:len(stack)-1]
            
            // 合并计算：preSign * 当前结果 + 之前结果
            res = preSign*res + preRes
        }
        // 忽略空格字符
    }

    return res
}

复杂度分析

时间复杂度

  • 时间复杂度：$O(n)$
  • 每个字符最多被访问一次，数字字符可能需要额外的内层循环来构建完整数字
  • 栈操作（入栈、出栈）都是 $O(1)$ 时间复杂度

空间复杂度

  • 空间复杂度：$O(n)$
  • 在最坏情况下（如 "((((1))))" ），栈的深度等于括号的嵌套深度
  • 最大嵌套深度可能达到 $O(n)$

关键收获

核心思想

  1. 栈处理括号：使用栈保存和恢复计算状态是处理嵌套结构的经典方法
  2. 符号传递：括号内外符号的正确传递是解题关键
  3. 状态管理：合理设计状态变量（res、sign、stack）

常见陷阱

  1. 多位数字处理：确保正确解析完整的数字，而不是单个字符
  2. 循环索引：内层数字解析循环后需要回退索引
  3. 符号初始化：进入新括号时要重置符号为正

扩展应用

  • 这种栈的状态保存技巧可应用于：
    • 表达式求值类问题
    • 括号匹配问题
    • 递归结构的迭代实现

相关问题

  • LeetCode 227: 基本计算器 II（处理乘除运算）
  • LeetCode 772: 基本计算器 III（同时处理加减乘除和括号）
  • LeetCode 394: 字符串解码（类似的栈状态保存思路）