LeetCode 385 迷你语法分析器

文章目录

• 摘要
• 描述
• 题解答案
• 题解代码分析
  • 1. 特殊情况处理
  • 2. 使用栈来维护嵌套结构
  • 3. 数字解析
  • 4. 处理逗号和右括号
  • 5. 完整解析流程示例
  • 6. 边界情况处理
• 示例测试及结果
  • 示例 1：单个整数
  • 示例 2：嵌套列表
  • 示例 3：包含负数
  • 示例 4：空列表
  • 示例 5：多层嵌套
• 时间复杂度
• 空间复杂度
• 实际应用场景
  • 场景一：JSON 解析
  • 场景二：配置文件解析
  • 场景三：表达式求值
  • 场景四：代码解析
  • 场景五：数据序列化和反序列化
• 总结

摘要

这道题其实挺有意思的，它要求我们实现一个语法分析器来解析嵌套列表的字符串表示。听起来像是编译原理的内容，但实际上用栈或者递归就能搞定。关键点在于如何正确处理嵌套结构，以及如何区分整数和列表。

这道题的核心在于如何解析类似 "[123,[456,[789]]]" 这样的字符串，把它转换成嵌套的数据结构。今天我们就用 Swift 来搞定这道题，顺便聊聊这种解析技术在实际开发中的应用场景，比如 JSON 解析、配置文件解析、表达式求值等等。

描述

题目要求是这样的：给定一个字符串 s 表示一个整数嵌套列表，实现一个解析它的语法分析器并返回解析的结果 NestedInteger。

列表中的每个元素只可能是整数或整数嵌套列表。

示例 1：

输入： s = "324", 输出： 324 解释： 你应该返回一个 NestedInteger 对象，其中只包含整数值 324。 

示例 2：

输入： s = "[123,[456,[789]]]", 输出： [123,[456,[789]]] 解释： 返回一个 NestedInteger 对象包含一个有两个元素的嵌套列表： 1. 一个 integer 包含值 123 2. 一个包含两个元素的嵌套列表： i. 一个 integer 包含值 456 ii. 一个包含一个元素的嵌套列表 a. 一个 integer 包含值 789 

提示：

• 1 <= s.length <= 5 * 10^4
• s 由数字、方括号 "[]"、负号 '-'、逗号 ',' 组成
• 用例保证 s 是可解析的 NestedInteger
• 输入中的所有值的范围是 [-10^6, 10^6]

这道题的核心思路是什么呢？我们需要遍历字符串，遇到 '[' 就创建一个新的嵌套列表，遇到 ']' 就结束当前列表，遇到数字就解析成整数，遇到逗号就分隔元素。我们可以用栈来维护嵌套结构，也可以用递归的方式来处理。

题解答案

下面是完整的 Swift 解决方案：

/** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * class NestedInteger { * // Return true if this NestedInteger holds a single integer, rather than a nested list. * public func isInteger() -> Bool * * // Return the single integer that this NestedInteger holds, if it holds a single integer * // Return nil if this NestedInteger holds a nested list * public func getInteger() -> Int? * * // Set this NestedInteger to hold a single integer. * public func setInteger(value: Int) * * // Set this NestedInteger to hold a nested list and adds a nested integer to it. * public func add(elem: NestedInteger) * * // Return the nested list that this NestedInteger holds, if it holds a nested list * // Return nil if this NestedInteger holds a single integer * public func getList() -> [NestedInteger]? * } */classSolution{funcdeserialize(_ s:String)->NestedInteger{// 如果字符串不以 '[' 开头，说明是单个整数if s.first !="["{let num =Int(s)??0let ni =NestedInteger() ni.setInteger(value: num)return ni }var stack:[NestedInteger]=[]var num:Int?=nilvar isNegative =falsefor char in s {if char =="["{// 遇到 '['，创建一个新的 NestedInteger 并压入栈let ni =NestedInteger() stack.append(ni)}elseif char =="-"{// 遇到负号，标记为负数 isNegative =true}elseif char.isNumber {// 遇到数字，累积数字let digit =Int(String(char))??0 num =(num ??0)*10+ digit }elseif char ==","|| char =="]"{// 遇到逗号或 ']'，处理之前累积的数字iflet n = num {let value = isNegative ?-n : n let ni =NestedInteger() ni.setInteger(value: value)// 将数字添加到栈顶的列表中iflet last = stack.last { last.add(elem: ni)}else{// 如果栈为空，说明这是最外层的单个数字 stack.append(ni)} num =nil isNegative =false}// 如果是 ']'，结束当前列表if char =="]"{if stack.count >1{// 弹出当前列表，添加到父列表中let current = stack.removeLast() stack.last?.add(elem: current)}}}}// 返回栈底的元素（最外层的列表）return stack.first ??NestedInteger()}}

题解代码分析

让我们一步步分析这个解决方案：

1. 特殊情况处理

首先，我们需要处理最简单的情况：如果字符串不以 '[' 开头，说明这是一个单独的整数，不需要解析嵌套结构。

if s.first !="["{let num =Int(s)??0let ni =NestedInteger() ni.setInteger(value: num)return ni }

这种情况对应示例 1，输入是 "324"，直接解析成整数返回即可。

2. 使用栈来维护嵌套结构

对于嵌套列表的情况，我们需要用栈来维护当前的嵌套层级：

var stack:[NestedInteger]=[]

栈的作用是：

• 当遇到 '[' 时，创建一个新的 NestedInteger 并压入栈，表示开始一个新的嵌套列表
• 当遇到 ']' 时，弹出栈顶的 NestedInteger，表示结束当前的嵌套列表
• 当遇到数字时，将数字添加到栈顶的 NestedInteger 中

3. 数字解析

我们需要处理数字的解析，包括：

• 多位数字的累积
• 负数的处理

var num:Int?=nilvar isNegative =false

当遇到数字字符时，我们累积数字：

elseif char.isNumber {let digit =Int(String(char))??0 num =(num ??0)*10+ digit }

当遇到负号时，我们标记为负数：

elseif char =="-"{ isNegative =true}

4. 处理逗号和右括号

当遇到逗号 ',' 或右括号 ']' 时，说明一个数字或列表元素结束了，我们需要处理之前累积的数字：

elseif char ==","|| char =="]"{// 处理之前累积的数字iflet n = num {let value = isNegative ?-n : n let ni =NestedInteger() ni.setInteger(value: value)// 将数字添加到栈顶的列表中iflet last = stack.last { last.add(elem: ni)}else{ stack.append(ni)} num =nil isNegative =false}// 如果是 ']'，结束当前列表if char =="]"{if stack.count >1{let current = stack.removeLast() stack.last?.add(elem: current)}}}

这里的逻辑是：

1. 如果有累积的数字，创建一个包含该数字的 NestedInteger，并添加到栈顶的列表中
2. 如果是 ']'，说明当前列表结束了，如果栈中还有父列表，就将当前列表添加到父列表中

5. 完整解析流程示例

让我们用一个例子来理解整个解析过程。假设输入是 "[123,[456,[789]]]"：

1. 遇到 '['：创建新的 NestedInteger，压入栈。栈：[list1]
2. 遇到 '1'、'2'、'3'：累积数字 123
3. 遇到 ','：创建包含 123 的 NestedInteger，添加到 list1。栈：[list1]，list1 包含 [123]
4. 遇到 '['：创建新的 NestedInteger，压入栈。栈：[list1, list2]
5. 遇到 '4'、'5'、'6'：累积数字 456
6. 遇到 ','：创建包含 456 的 NestedInteger，添加到 list2。栈：[list1, list2]，list2 包含 [456]
7. 遇到 '['：创建新的 NestedInteger，压入栈。栈：[list1, list2, list3]
8. 遇到 '7'、'8'、'9'：累积数字 789
9. 遇到 ']'：创建包含 789 的 NestedInteger，添加到 list3。然后弹出 list3，添加到 list2。栈：[list1, list2]，list2 包含 [456, [789]]
10. 遇到 ']'：弹出 list2，添加到 list1。栈：[list1]，list1 包含 [123, [456, [789]]]
11. 遇到 ']'：结束。返回 list1

6. 边界情况处理

代码中处理了几个重要的边界情况：

1. 单个整数：如果字符串不以 '[' 开头，直接解析为整数
2. 空列表：如果遇到 "[]"，会创建一个空的 NestedInteger
3. 负数：正确处理负号，将数字标记为负数
4. 栈为空：如果栈为空但遇到数字，说明这是最外层的单个数字

示例测试及结果

让我们用几个例子来测试一下这个解决方案：

示例 1：单个整数

输入：s = "324"

执行过程：

1. 检查第一个字符：'3' 不是 '['，进入单个整数分支
2. 解析整数：Int("324") = 324
3. 创建 NestedInteger 并设置值为 324
4. 返回结果

**结果：**返回包含整数 324 的 NestedInteger

示例 2：嵌套列表

输入：s = "[123,[456,[789]]]"

执行过程：

1. 第一个字符是 '['，进入嵌套列表解析
2. 创建 list1，压入栈
3. 解析数字 123，添加到 list1
4. 遇到 ','，继续
5. 遇到 '['，创建 list2，压入栈
6. 解析数字 456，添加到 list2
7. 遇到 ','，继续
8. 遇到 '['，创建 list3，压入栈
9. 解析数字 789，添加到 list3
10. 遇到 ']'，弹出 list3，添加到 list2
11. 遇到 ']'，弹出 list2，添加到 list1
12. 遇到 ']'，结束

**结果：**返回包含 [123, [456, [789]]] 的 NestedInteger

示例 3：包含负数

输入：s = "[-123,[456]]"

执行过程：

1. 遇到 '['，创建 list1
2. 遇到 '-'，标记 isNegative = true
3. 解析数字 123，因为是负数，所以值是 -123
4. 添加到 list1
5. 遇到 ','，继续
6. 遇到 '['，创建 list2
7. 解析数字 456，添加到 list2
8. 遇到 ']'，弹出 list2，添加到 list1
9. 遇到 ']'，结束

**结果：**返回包含 [-123, [456]] 的 NestedInteger

示例 4：空列表

输入：s = "[]"

执行过程：

1. 遇到 '['，创建 list1
2. 遇到 ']'，结束当前列表

**结果：**返回空的 NestedInteger（不包含任何元素）

示例 5：多层嵌套

输入：s = "[[[1]]]"

执行过程：

1. 遇到 '['，创建 list1
2. 遇到 '['，创建 list2
3. 遇到 '['，创建 list3
4. 解析数字 1，添加到 list3
5. 遇到 ']'，弹出 list3，添加到 list2
6. 遇到 ']'，弹出 list2，添加到 list1
7. 遇到 ']'，结束

**结果：**返回包含 [[[1]]] 的 NestedInteger

时间复杂度

让我们分析一下这个算法的时间复杂度：

时间复杂度：O(n)

其中 n 是字符串 s 的长度。

分析：

1. 遍历字符串：我们需要遍历整个字符串一次，时间复杂度 O(n)
2. 栈操作：每个字符最多进行一次栈操作（压入或弹出），栈操作的时间复杂度是 O(1)
3. 数字解析：每个数字字符只处理一次，时间复杂度 O(1)
4. 创建 NestedInteger：每个元素最多创建一次 NestedInteger，时间复杂度 O(1)

所以总时间复杂度是 O(n)，这是最优的，因为我们至少需要遍历一次字符串来解析它。

对于题目约束（s.length <= 5 * 10^4），这个时间复杂度是完全可接受的。

空间复杂度

让我们分析一下这个算法的空间复杂度：

空间复杂度：O(n)

其中 n 是字符串 s 的长度。

分析：

1. 栈空间：栈的深度最多等于嵌套的层数。在最坏情况下（比如 "[[[[...]]]]"），栈的深度是 O(n)。但实际上，由于字符串格式的限制，嵌套层数不会太深
2. NestedInteger 对象：我们需要创建 O(n) 个 NestedInteger 对象（每个数字和每个列表都需要一个对象）
3. 临时变量：num、isNegative 等临时变量占用 O(1) 空间

所以总空间复杂度是 O(n)，这是必要的，因为我们需要存储解析后的数据结构。

实际应用场景

这种语法解析技术在实际开发中应用非常广泛：

场景一：JSON 解析

JSON 解析器的工作原理和这道题类似，都是解析嵌套的数据结构。比如解析 {"name": "John", "age": 30, "hobbies": ["reading", "coding"]} 这样的 JSON 字符串，需要处理对象、数组、字符串、数字等不同类型的嵌套结构。

在实际项目中，我们可以使用 Swift 的 Codable 协议来解析 JSON，但理解底层的解析原理对于调试和优化很有帮助。

场景二：配置文件解析

很多配置文件都使用嵌套结构，比如 YAML、XML、TOML 等。解析这些配置文件时，我们需要处理嵌套的键值对、列表等结构。

比如解析这样的 YAML 配置：

database:host: localhost port:3306connections:-name: primary pool:10-name: secondary pool:5

解析器需要处理嵌套的对象和列表结构。

场景三：表达式求值

在计算器或表达式求值器中，我们需要解析数学表达式，比如 "1 + 2 * (3 + 4)"。虽然这种表达式不是嵌套列表，但解析思路类似：使用栈来处理运算符优先级和括号嵌套。

场景四：代码解析

在编译器或解释器中，我们需要解析源代码，构建抽象语法树（AST）。这个过程也需要处理嵌套的结构，比如函数定义、类定义、控制流语句等。

场景五：数据序列化和反序列化

在数据序列化和反序列化中，我们需要将内存中的数据结构转换成字符串，或者将字符串解析回数据结构。这个过程也需要处理嵌套结构。

总结

这道题虽然看起来复杂，但实际上是一个经典的栈应用问题。通过使用栈来维护嵌套结构，我们可以清晰地处理各种情况。

关键点总结：

1. 栈的应用：使用栈来维护嵌套列表的层级关系
2. 字符分类处理：根据不同的字符（'['、']'、数字、','、'-'）进行不同的处理
3. 数字累积：多位数字需要累积处理
4. 边界情况：需要处理单个整数、空列表、负数等特殊情况

算法优势：

1. 时间复杂度低：只需要遍历一次字符串，O(n)
2. 实现简单：逻辑清晰，容易理解和维护
3. 扩展性好：可以很容易地扩展到处理更复杂的语法

实际应用：

语法解析技术在 JSON 解析、配置文件解析、表达式求值、代码解析等场景中都有广泛应用。理解这种解析技术，不仅能帮助我们解决类似的算法题，还能让我们更好地理解各种解析器的工作原理。

希望这篇文章能帮助你理解语法解析的基本思路，以及如何在实际开发中应用这种技术！