LeetCode 385 迷你语法分析器

摘要

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

这道题的核心在于如何解析类似"[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{// 如果字符串不以 '[' 开头，说明是单个整数ifs.first!="["{letnum=Int(s)??0letni=NestedInteger()ni.setInteger(value:num)returnni}varstack:[NestedInteger]=[]varnum:Int?=nilvarisNegative=falseforcharins{ifchar=="["{// 遇到 '['，创建一个新的 NestedInteger 并压入栈letni=NestedInteger()stack.append(ni)}elseifchar=="-"{// 遇到负号，标记为负数isNegative=true}elseifchar.isNumber{// 遇到数字，累积数字letdigit=Int(String(char))??0num=(num??0)*10+digit}elseifchar==","||char=="]"{// 遇到逗号或 ']'，处理之前累积的数字ifletn=num{letvalue=isNegative?-n:nletni=NestedInteger()ni.setInteger(value:value)// 将数字添加到栈顶的列表中ifletlast=stack.last{last.add(elem:ni)}else{// 如果栈为空，说明这是最外层的单个数字stack.append(ni)}num=nilisNegative=false}// 如果是 ']'，结束当前列表ifchar=="]"{ifstack.count>1{// 弹出当前列表，添加到父列表中letcurrent=stack.removeLast()stack.last?.add(elem:current)}}}}// 返回栈底的元素（最外层的列表）returnstack.first??NestedInteger()}}

题解代码分析

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

1. 特殊情况处理

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

ifs.first!="["{letnum=Int(s)??0letni=NestedInteger()ni.setInteger(value:num)returnni}

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

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

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

varstack:[NestedInteger]=[]

栈的作用是：

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

3. 数字解析

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

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

varnum:Int?=nilvarisNegative=false

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

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

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

elseifchar=="-"{isNegative=true}

4. 处理逗号和右括号

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

elseifchar==","||char=="]"{// 处理之前累积的数字ifletn=num{letvalue=isNegative?-n:nletni=NestedInteger()ni.setInteger(value:value)// 将数字添加到栈顶的列表中ifletlast=stack.last{last.add(elem:ni)}else{stack.append(ni)}num=nilisNegative=false}// 如果是 ']'，结束当前列表ifchar=="]"{ifstack.count>1{letcurrent=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:localhostport:3306connections:-name:primarypool:10-name:secondarypool:5

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

场景三：表达式求值

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

场景四：代码解析

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

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

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

总结

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

关键点总结：

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

算法优势：

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

实际应用：

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

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