原题

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

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

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

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

示例 1：

给定 s = "324",

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

示例 2：

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

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

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

解法

本题解同步发于leetcode题解区：java递归 2ms 100%

捷报：发于leetcode的题解已经成为Java分类下阅读量最高的一篇，也是我写的所有题解中点赞数最多的一篇?

思想

见代码部分

代码

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

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

class Solution {
    //递归函数通过字符数组和cur下标确定要处理的位置l
    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;
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode385-%e8%bf%b7%e4%bd%a0%e8%af%ad%e6%b3%95%e5%88%86%e6%9e%90%e5%99%a8/

leetcode385-迷你语法分析器

原题

解法

思想

代码

发表回复

leetcode385-迷你语法分析器

原题

解法

思想

代码

相关推荐

发表回复