0385. 迷你语法分析器【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 栈解析

1. 📝 题目描述

• leetcode

给定一个字符串 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]

2. 🎯 s.1 - 栈解析

c

// LeetCode C 接口当前不支持此题的 C 语言提交
// 以下为伪代码思路：
// 1. 若字符串不以 '[' 开头，直接解析为整数
// 2. 用栈处理嵌套结构，遇 '[' 压栈，遇 ']' 弹栈并合并

js

/**
 * @param {string} s
 * @return {NestedInteger}
 */
var deserialize = function (s) {
  if (s[0] !== '[') return new NestedInteger(parseInt(s))
  const stack = []
  let num = '',
    hasNum = false
  for (const ch of s) {
    if (ch === '[') {
      stack.push(new NestedInteger())
    } else if (ch === ']') {
      if (hasNum) {
        stack[stack.length - 1].add(new NestedInteger(parseInt(num)))
        num = ''
        hasNum = false
      }
      if (stack.length > 1) {
        const top = stack.pop()
        stack[stack.length - 1].add(top)
      }
    } else if (ch === ',') {
      if (hasNum) {
        stack[stack.length - 1].add(new NestedInteger(parseInt(num)))
        num = ''
        hasNum = false
      }
    } else {
      num += ch
      hasNum = true
    }
  }
  return stack[0]
}

py

class Solution:
    def deserialize(self, s: str) -> NestedInteger:
        if s[0] != '[':
            return NestedInteger(int(s))
        stack = []
        num, has_num = '', False
        for ch in s:
            if ch == '[':
                stack.append(NestedInteger())
            elif ch == ']':
                if has_num:
                    stack[-1].add(NestedInteger(int(num)))
                    num, has_num = '', False
                if len(stack) > 1:
                    top = stack.pop()
                    stack[-1].add(top)
            elif ch == ',':
                if has_num:
                    stack[-1].add(NestedInteger(int(num)))
                    num, has_num = '', False
            else:
                num += ch
                has_num = True
        return stack[0]

• 时间复杂度：$O(n)$，其中 $n$ 是字符串长度
• 空间复杂度：$O(d)$，其中 $d$ 是嵌套深度

算法思路：

• 遇 [ 压入新 NestedInteger，遇数字则累加
• 遇 , 或 ] 时将累积的数字加入栈顶元素
• 遇 ] 时弹栈并合并到父层