LeetCode 385. 迷你语法分析器
目录
题目描述
题意分析
题目目标：输入是一个描述嵌套列表的字符串，比如
"[123,[456,[789]]]"，要求把它还原成 NestedInteger 结构——这个结构要么持有一个整数，要么持有一个由 NestedInteger 组成的列表，两者互斥。
核心约束：这是一道纯粹的解析题，输入保证格式合法，所以不需要做任何错误恢复，只需要按语法规则把字符流翻译成树形结构。语法本身是递归定义的（一个元素要么是整数，要么是被方括号包裹的、用逗号分隔的元素序列），而递归定义的语言天然对应两种实现方式：显式递归下降，或者用一个栈把递归展平。第二个信号是括号必然配对且嵌套，这正是栈结构的典型适用场景——「后进先出」恰好对应「最内层的列表最先闭合」。
边界处理：输入可能根本没有方括号，此时整个串就是一个纯整数，必须走单独分支直接构造整数型 NestedInteger；数字可能是负数，减号紧贴在数字前面，扫描时要把它和数字一起吃掉；数字可能是多位的，不能一个字符一个字符地当成独立元素；空列表"[]"是合法输入，应当返回一个空列表而不是抛异常；嵌套层数可能很深，实现要能处理任意深度；构造整数型和列表型 NestedInteger 的接口不同，混用会得到语义错误的结果。
解法：栈模拟解析
核心思路
输入语法只有整数、逗号和成对方括号。纯整数没有列表上下文，可以直接构造整数型
NestedInteger；列表输入则用栈保存所有尚未闭合的列表，避免递归解析在深嵌套下占用调用栈。扫描时有三类动作：遇到
[新建空列表并压栈；遇到数字或负号，记录数字起点；遇到,或]，若前面有数字就解析完整整数并加入栈顶。]还表示当前列表完成：将其弹出，若栈已空则它是根，否则加入父列表。栈不变量：栈从底到顶依次保存当前位置所属的所有未闭合列表，栈顶是当前正在接收元素的列表；
numberStart为-1，或指向尚未提交的整数起点。正确性：每个整数只在其分隔符处提交一次；每个
[创建一层列表，每个匹配的]完成同一层并挂到唯一父列表。合法输入的嵌套顺序与栈的后进先出完全一致，因此最终弹出的外层对象与输入结构相同。
解题步骤
- 若首字符不是
[, 直接解析整个字符串为整数。- 从左到右扫描；
[压入空列表，数字或-记录整数起点。- 遇到
,或]时，先把待处理整数解析并加入栈顶。- 遇到
]再弹出完成的列表：栈空则返回，否则加入父列表。
"[123,[456,[789]]]"会按关闭顺序完成最内层[789]、中层[456,[789]]、外层整体。"[-1,[]]"同时验证负数和空列表；纯整数"324"不进入栈流程。
代码实现
import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
public NestedInteger deserialize(String s) {
if (s.charAt(0) != '[') {
return new NestedInteger(Integer.parseInt(s));
}
Deque<NestedInteger> stack = new ArrayDeque<>();
int numberStart = -1;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '[') {
stack.push(new NestedInteger());
} else if (ch == '-' || Character.isDigit(ch)) {
if (numberStart == -1) {
numberStart = i;
}
} else {
if (numberStart != -1) {
int value = Integer.parseInt(s.substring(numberStart, i));
stack.peek().add(new NestedInteger(value));
numberStart = -1;
}
if (ch == ']') {
NestedInteger completed = stack.pop();
if (stack.isEmpty()) {
return completed;
}
stack.peek().add(completed);
}
}
}
return new NestedInteger();
}
}
import "strconv"
func deserialize(s string) *NestedInteger {
if s[0] != '[' {
value, _ := strconv.Atoi(s)
result := &NestedInteger{}
result.SetInteger(value)
return result
}
stack := make([]*NestedInteger, 0)
numberStart := -1
for i := 0; i < len(s); i++ {
ch := s[i]
if ch == '[' {
stack = append(stack, &NestedInteger{})
} else if ch == '-' || ch >= '0' && ch <= '9' {
if numberStart == -1 {
numberStart = i
}
} else {
if numberStart != -1 {
value, _ := strconv.Atoi(s[numberStart:i])
integer := &NestedInteger{}
integer.SetInteger(value)
stack[len(stack)-1].Add(*integer)
numberStart = -1
}
if ch == ']' {
completed := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if len(stack) == 0 {
return completed
}
stack[len(stack)-1].Add(*completed)
}
}
}
return &NestedInteger{}
}
复杂度分析
- 时间复杂度：$O(n)$。每个字符被扫描常数次，所有整数片段的总长度不超过输入长度。
- 空间复杂度：$O(d)$，其中
d是最大嵌套深度；返回的NestedInteger结构不计入额外空间。
关键点总结
- 栈保存未闭合的列表上下文，
[入栈、]出栈并挂回父层。- 负号和连续数字必须作为一个完整整数解析。
- 纯整数没有列表栈，需要在入口单独处理。
- 空列表由“压入后未添加元素便弹出”自然表示。
易错点总结
- 纯整数仍走列表流程：栈为空时添加元素会崩溃。
- 逐字符构造整数：
123会被错误解析成三个元素。- 闭合子列表后不加入父列表：嵌套结构会丢失。
- 最外层弹出后仍访问栈顶：此时栈已空，应直接返回完成对象。
- 遗漏负号：负数会被解析成正数或导致扫描停滞。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 341. 扁平化嵌套列表迭代器 | 中等 | 输入已是 NestedInteger 结构，考察的是把嵌套压平并支持惰性迭代 |
| 394. 字符串解码 | 中等 | 同为括号嵌套的栈模拟，但要同时压入重复次数和已构建的前缀，栈里存两类信息 |
| 20. 有效的括号 | 简单 | 只需判断配对合法性，不构造结构，是本题栈机制的最简形态 |
| 224. 基本计算器 | 困难 | 括号嵌套之上还要处理运算符优先级与正负号，栈中保存的是待恢复的符号与累加值 |
| 726. 原子的数量 | 困难 | 嵌套括号带乘数系数，需要在弹栈时把整层计数按倍数合并回父层 |
| 8. 字符串转换整数 (atoi) | 中等 | 专注于词法层面的整数扫描，重点是符号、前导空格与溢出截断 |