LeetCode 385. 迷你语法分析器
题目描述
题意分析
将字符串解析为
NestedInteger：它既可以表示一个整数，也可以表示由若干NestedInteger组成的列表。列表可以为空，也可以继续嵌套，结果必须保留元素顺序与括号所表达的层级。题目保证输入非空、语法合法，只含数字、负号、逗号和方括号，整数值处于给定范围内。因此这里只负责构造结构，不需要补充非法输入的校验或容错规则。纯整数也是合法的整体输入，并不一定包在列表中。
解法：栈模拟解析
核心思路
[!blue]
嵌套括号需要先完成内层，再回到外层继续添加元素，这正好符合栈的后进先出顺序。栈从底到顶保存所有已经读到左括号、尚未闭合的列表，栈顶就是当前整数或子列表应该加入的那一层。
遇到
[时创建空列表并入栈，开始处理它的内部。数字可能有多位并带负号，不能逐个字符创建整数；用numberStart记录整个整数片段的起点，-1表示当前没有待提交的数字。遇到后续数字时继续向前扫描即可。逗号或右括号意味着一个数字片段已经结束。若起点不是
-1，先解析[numberStart,i)，创建整数节点加入栈顶，再清空起点。这里用“是否存在片段”判断，整数值为零也会正常提交；空列表则没有片段，不会尝试解析空串。如果当前字符是
]，提交末尾数字后再弹出已经完成的列表。栈中还有父层时，把这个完整子列表作为一个元素加入父层；栈已空时，闭合的就是最外层列表，直接返回。所有元素在输入中结束时依次加入所属列表，因此原顺序和嵌套关系都被保留。纯整数没有括号或分隔符，也没有可以接收它的列表栈，所以入口发现首字符不是
[时直接解析整个字符串，构造整数结果。列表分支则由最外层右括号完成返回。
解题步骤
- 首字符不是左括号时，直接解析并返回一个整数节点。
- 否则创建空栈，令
numberStart = -1，逐字符扫描。- 左括号建立新列表；数字或负号只在当前还没有起点时设置
numberStart。- 遇到逗号或右括号，先提交可能存在的整数片段；若是右括号，再弹出完整列表，加入父层或返回最外层结果。
子列表闭合后的逗号只起分隔作用，此时数字起点已经清空，不会重复创建元素。Go 忽略整数转换错误，是因为题目保证数字片段合法且值在可表示范围内。
代码实现
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(L)$，其中 $L$ 为输入长度。每个括号或分隔符处理一次，数字片段的解析总长度也不超过 $L$。
- 空间复杂度：辅助栈为 $O(d+1)$，其中 $d$ 为嵌套深度；题目整数范围固定，单个数字片段的临时空间为常数。返回结构最多占 $O(L)$，不计入辅助栈空间。
关键点总结
[!green]
- 先提交末尾数字，再关闭当前列表。
- 负号和后续数字属于同一个整数片段。
- 空列表没有待提交数字，直接完成当前栈层。
易错点总结
[!yellow]
- 逐字符创建整数：多位数被拆成多个元素。
- 闭合后不挂回父列表：子结构丢失。
- 外层弹出后继续访问栈顶：栈已经为空。
- 数字提交后不重置起点：后续分隔符会重复解析旧片段。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 341. 扁平化嵌套列表迭代器 | 中等 | 原题遍历已有嵌套整数结构，本题先从带括号文本构造这个结构。 |
| 394. 字符串解码 | 中等 | 同样解析带嵌套括号的文本，但原题括号外数字表示重复次数，本题数字是数据节点。 |