加载中…迷你语法分析器（力扣网）
(2022-04-16 11:22:31)
标签：
js |
分类： Html.css.js |
给定一个字符串 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
来源：力扣（LeetCode）
if(s[0]!="[")return (parseInt(s));
var
res = [],str='';
for(var
i = 0;i
< s.length; i++){
if(s[i]=="["){
res.push([]);
} else if(s[i]==','){
if(str.length>0){
res[res.length-1].push(parseInt(str));
str
= '';
}
} else if(s[i]=="]"){
var top =
res.pop();
if(str.length>0){
top.push(parseInt(str));
str
= '';
}
if(res.length == 0)return top;
res[res.length-1].push(top);
} else{
str+=s[i];
}
}
};
列表中的每个元素只可能是整数或整数嵌套列表
输入：s = "324",
输出：324
解释：你应该返回一个 NestedInteger 对象，其中只包含整数值 324。
示例 2：
输入：s = "[123,[456,[789]]]",
输出：[123,[456,[789]]]
解释：返回一个 NestedInteger 对象包含一个有两个元素的嵌套列表：
1. 一个 integer 包含值 123
2. 一个包含两个元素的嵌套列表：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/mini-parser
这个题我说一下解题的思路，因为这里有给一个构造函数，里面封装了一下方法，我也就不复制过来了。
我就简化一点，这个题可以视为解析一个多维数组的字符串。
下面先上代码（这个代码提交到力扣是不能通过的，代码需要用到题中的那个构造函数）：
var deserialize = function(s)
{
下面就说一下思路：
此题我最开始思索了很久，这就是如何将一个一维数组按照一定规律进行升维，变成多维数组。
这里有几个关键点，如果是纯数字，字符串第一个符合必定不是 ‘[’，这里可以排除一种情况。
然后就是需要进行升维的情况，
遇到 '[' ，说明维度在增加；
遇到 ']' ，说明此维度结束；
遇到 ',' ，说明有一个新的数组元素。
这么一分析看着是很简单了，但问题是如何升维。
最开始，我是想着用一个数组存数字元素，一个二维数组存所在维度子元素的长度以及自身相对父元素的位置，等遍历完字符串，再将两个数组进结合拼接出新数组。
但随着深入解析，这种操作复杂而且难度大。
到此，不得不拿出我的看家法宝--翻看他人解题思路。
细看了几人的解题思路，顿时豁然开朗，这个题用堆栈就可以解决，何须我那么复杂的操作，又是存数字，又是存维度啥的。
下面说说堆栈的思路：
首先，需要一个str来接收每一串数字，即当字符串 s[i] !='[
, ]' 这三种情况之外，str+=s[i],
然后就是一个堆栈 res，往里面塞入一个新数组的条件，就是遇到 '['，即res.push([])
接着就是出栈，出栈就是遇到 ']'，即res.pop()，并且将这个出栈的数组用top保存，
如果str.length>0,说明在']'前面还有一个数字，这个数字需要插入到top里面，他是top里的数组元素，即，top.push(parseInt(str))。
如果res.length==0，是不是说明这个栈里的数据都出完了，把top返回出去
那如果res.length>0,那么就将top插入到res的最后一个子元素里，即res[res.length-1].push(top)（这里是关键）
为何这么做？
大家可以这么想，一个数组的开始是 '['，他的结束是 ']'，这个没问题吧
那么当遇到 ']' ,是不是说明res里的最后一个子数字出栈，他是不是要变成前面一个res子数组的元素，因为前面一个子数组的
']' 没有出现。这里弄明白了，此题就不是问题。
至于遇到 ',' ，就直接 res[res.length-1].push(parseInt(str))
此题思路就是这样，希望对各位看官有用
喜欢
0
赠金笔
前一篇：括号生成（力扣网）
后一篇：最大回文数乘积（力扣网）