原文链接: https://leetcode-cn.com/problems/mini-parser

英文原文

Given a string s represents the serialization of a nested list, implement a parser to deserialize it and return the deserialized NestedInteger.

Each element is either an integer or a list whose elements may also be integers or other lists.

 

Example 1:

Input: s = "324"
Output: 324
Explanation: You should return a NestedInteger object which contains a single integer 324.

Example 2:

Input: s = "[123,[456,[789]]]"
Output: [123,[456,[789]]]
Explanation: Return a NestedInteger object containing a nested list with 2 elements:
1. An integer containing value 123.
2. A nested list containing two elements:
    i.  An integer containing value 456.
    ii. A nested list with one element:
         a. An integer containing value 789

 

Constraints:

• 1 <= s.length <= 5 * 104
• s consists of digits, square brackets "[]", negative sign '-', and commas ','.
• s is the serialization of valid NestedInteger.
• All the values in the input are in the range [-106, 106].

中文题目

给定一个用字符串表示的整数的嵌套列表，实现一个解析它的语法分析器。

列表中的每个元素只可能是整数或整数嵌套列表

提示：你可以假定这些字符串都是格式良好的：

• 字符串非空
• 字符串不包含空格
• 字符串只包含数字0-9、[、-、,、]

 

示例 1：

给定 s = "324",

你应该返回一个 NestedInteger 对象，其中只包含整数值 324。

示例 2：

给定 s = "[123,[456,[789]]]",

返回一个 NestedInteger 对象包含一个有两个元素的嵌套列表：

1. 一个 integer 包含值 123
2. 一个包含两个元素的嵌套列表：
    i.  一个 integer 包含值 456
    ii. 一个包含一个元素的嵌套列表
         a. 一个 integer 包含值 789

通过代码

高赞题解

设定一个getNest()函数用于返回一个列表类型的NestedInteger。

重要的思想是通过类的全局字符数组和一个下标值让每次调用递归函数都知道要处理哪个位置。

class Solution {

    //递归函数通过字符数组和cur下标确定要处理的位置

    char[] chars;

    int cur = 0;

    public NestedInteger deserialize(String s) {

        chars = s.toCharArray();

        //本身不是一个集合而是一个整数的情况

        if(chars[0]!='[') return new NestedInteger(Integer.valueOf(s));

        //调用递归函数返回根集合

        return getNest();

    }

    public NestedInteger getNest(){

        NestedInteger nest = new NestedInteger();

        int num = 0;//num用于缓存用逗号分割的整数类型的值

        boolean negative = false;//当前记录的整数是不是负数

        while(cur!=chars.length-1){

            cur ++;

            if(chars[cur]==',') continue;

            if(chars[cur]=='[') nest.add(getNest());//遇到[递归获取子集合

            else if(chars[cur]==']') return nest;

            else if(chars[cur]=='-') negative = true;

            else{//是数字的情况

                if(negative) num = 10*num - (chars[cur]-48);

                else num = 10*num + (chars[cur]-48);

                //如果下一个字符是,或者]说明当前数字已经记录完了，需要加入集合中

                if(chars[cur+1]==','||chars[cur+1]==']'){ 

                    nest.add(new NestedInteger(num));

                    num = 0;

                    negative = false;

                }

            }

        }

        return null;

    }

}

2020/06/08编辑：写这篇题解的时候刚开始用Java刷题不久，写的代码不是很优雅，这个代码有几处地方可以修改一下让代码更清晰规范一些：

• 这段代码中的48代表的就是字符'0'，建议使用'0'替换48。

• negative是布尔型，其实可以优化成整型sign，后面就不需要用if-else进行判断，代码更加精炼。

优化后的代码如下：

class Solution {

    //递归函数通过字符数组和cur下标确定要处理的位置

    char[] chars;

    int cur = 0;

    public NestedInteger deserialize(String s) {

        chars = s.toCharArray();

        //本身不是一个集合而是一个整数的情况

        if(chars[0]!='[') return new NestedInteger(Integer.valueOf(s));

        //调用递归函数返回根集合

        return getNest();

    }

    public NestedInteger getNest(){

        NestedInteger nest = new NestedInteger();

        int num = 0;//num用于缓存用逗号分割的整数类型的值

        int sign = 1;//当前记录的整数的符号，1代表整数，-1代表负数

        while(cur!=chars.length-1){

            cur ++;

            if(chars[cur]==',') continue;

            if(chars[cur]=='[') nest.add(getNest());//遇到[递归获取子集合

            else if(chars[cur]==']') return nest;

            else if(chars[cur]=='-') sign = -1;

            else{//是数字的情况

                num = 10*num + sign * (chars[cur]-'0');

                //如果下一个字符是,或者]说明当前数字已经记录完了，需要加入集合中

                if(chars[cur+1]==','||chars[cur+1]==']'){ 

                    nest.add(new NestedInteger(num));

                    num = 0;

                    sign = 1;

                }

            }

        }

        return null;

    }

}

统计信息

通过次数	提交次数	AC比率
7698	18390	41.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
扁平化嵌套列表迭代器	中等
三元表达式解析器	中等
删除注释	中等