385.mini-parser.md

题目地址(385. 迷你语法分析器)

https://leetcode-cn.com/problems/mini-parser/

题目描述

给定一个用字符串表示的整数的嵌套列表，实现一个解析它的语法分析器。 列表中的每个元素只可能是整数或整数嵌套列表 提示：你可以假定这些字符串都是格式良好的： 字符串非空 字符串不包含空格 字符串只包含数字0-9、[、-、,、]   示例 1： 给定 s = "324", 你应该返回一个 NestedInteger 对象，其中只包含整数值 324。 示例 2： 给定 s = "[123,[456,[789]]]", 返回一个 NestedInteger 对象包含一个有两个元素的嵌套列表： 1. 一个 integer 包含值 123 2. 一个包含两个元素的嵌套列表： i. 一个 integer 包含值 456 ii. 一个包含一个元素的嵌套列表 a. 一个 integer 包含值 789 

前置知识

• 栈
• 递归

公司

• 暂无

思路

我们可以直接使用 eval 来将字符串转化为数组。

classSolution: defdeserialize(self, s: str) ->NestedInteger: defdfs(cur): iftype(cur) ==int: returnNestedInteger(cur) ans=NestedInteger() fornxtincur: ans.add(dfs(nxt)) returnansreturndfs(eval(s))

接下来，我们考虑如何实现 eval。

这其实是一个简单的栈 + dfs 题目。力扣中有非常多的题目都使用了这个题目，比如一些编码解码的题目，eg：394. 字符串解码。

关键点

• 栈+递归。遇到 [ 开启新的递归，遇到 ] 返回

代码

• 语言支持：Python3

Python3 Code:

# """# 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]# """classSolution: defdeserialize(self, s: str) ->NestedInteger: defdfs(cur): iftype(cur) ==int: returnNestedInteger(cur) ans=NestedInteger() fornxtincur: ans.add(dfs(nxt)) returnansdefto_array(i): stack= [] num=''whilei<len(s): ifs[i] ==' ': i+=1continueelifs[i] ==',': ifnum: stack.append(int(numor'0')) num=''elifs[i] =='[': j, t=to_array(i+1) stack.append(t) i=jelifs[i] ==']': breakelse: num+=s[i] i+=1ifnum: stack.append(int(num)) returni, stackreturndfs(to_array(0)[1][0])

复杂度分析

令 n 为 s 长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。