迷你语法分析器

难度: Medium

给定一个字符串 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⁴
s 由数字、方括号 "[]"、负号 '-' 、逗号 ','组成
用例保证 s 是可解析的 NestedInteger
输入中的所有值的范围是 [-10⁶, 10⁶]

Submission

运行时间: 28 ms

内存: 18.4 MB

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
#    def __init__(self, value=None):
#        """
#        If value is not specified, initializes an empty list.
#        Otherwise initializes a single integer equal to value.
#        """
#
#    def isInteger(self):
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        :rtype bool
#        """
#
#    def add(self, elem):
#        """
#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
#        :rtype void
#        """
#
#    def setInteger(self, value):
#        """
#        Set this NestedInteger to hold a single integer equal to value.
#        :rtype void
#        """
#
#    def getInteger(self):
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        :rtype int
#        """
#
#    def getList(self):
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        :rtype List[NestedInteger]
#        """
class Solution:
    def deserialize(self, s: str) -> NestedInteger:

        if s[0] != '[':
            return NestedInteger(int(s))

        # flag用来标记是否是负数
        st, num, flag = [], 0, 1

        
        for index, letter in enumerate(s):
            
            # 如果遍历到一个符号，那就把flag改成-1
            if letter == '-':
                flag = -1
            elif letter.isdigit():
                num = num * 10 + int(letter)
            elif letter == '[':
                st.append(NestedInteger())
            elif letter in ',]':
                if s[index - 1].isdigit():
                    st[-1].add(NestedInteger(flag * num))
                    num, flag = 0, 1
                if letter == ']' and len(st) > 1:
                    st[-2].add(st.pop())
        return st.pop()

Explain

这个题解使用了栈来解析嵌套列表。它逐个字符遍历输入字符串 s，根据不同的字符进行相应的操作： 1. 如果当前字符是数字，就更新当前的数字 num。 2. 如果当前字符是 '-'，就将 flag 设为 -1，表示当前数字是负数。 3. 如果当前字符是 '['，就在栈中添加一个新的 NestedInteger 对象。 4. 如果当前字符是 ',' 或 ']'，且前一个字符是数字，就将当前数字 num 转换成 NestedInteger 对象，并将其添加到栈顶的 NestedInteger 中，然后将 num 和 flag 重置。 5. 如果当前字符是 ']'，且栈中有多个元素，就将栈顶的 NestedInteger 对象弹出，并将其添加到新的栈顶 NestedInteger 中。 6. 最后，栈中唯一剩下的 NestedInteger 对象就是解析后的结果。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def deserialize(self, s: str) -> NestedInteger:
        if s[0] != '[':
            return NestedInteger(int(s))

        # flag 用来标记是否是负数
        st, num, flag = [], 0, 1

        for index, letter in enumerate(s):
            # 如果遍历到一个符号，那就把 flag 改成 -1
            if letter == '-':
                flag = -1
            elif letter.isdigit():
                num = num * 10 + int(letter)
            elif letter == '[':
                st.append(NestedInteger())
            elif letter in ',]':
                if s[index - 1].isdigit():
                    st[-1].add(NestedInteger(flag * num))
                    num, flag = 0, 1
                if letter == ']' and len(st) > 1:
                    st[-2].add(st.pop())
        return st.pop()

Explore

题解中的算法没有直接处理输入字符串为空或只含空格的情况。在实际应用中，这样的输入应当被认为是无效的。如果需要容错处理，可以在函数开始时添加条件检查，如果输入字符串为空或全为空格，则返回一个空的NestedInteger对象或抛出一个异常。

栈是一种后进先出的数据结构，非常适合处理具有嵌套结构的数据，例如本题中的嵌套列表。使用栈可以方便地处理和回溯嵌套关系，因为一旦完成内层列表的解析，可以立刻将其加入到上一层的列表中。而使用队列或链表虽然也可实现，但在处理嵌套的回溯上更复杂，效率可能也较低。

题解中通过连续读取数字字符并使用累乘和累加的方式（num = num * 10 + int(letter)）构建多位数，这确保了多位数可以被正确解析。同时，通过引入flag变量，当遇到负号时，将flag设置为-1，这样在添加数字到NestedInteger对象时，可以通过乘以flag来处理负数情况，确保数字的正负正确。

题解中确实没有详细说明如何处理格式错误的输入，包括连续的','字符。理想的做法是在解析过程中增加对输入格式的校验。例如，可以检查连续的','是否出现，或者在不应出现数字的地方出现数字等情况，并在发现格式错误时抛出异常或返回错误信息。这样可以避免解析非法格式的输入，增强代码的鲁棒性。