十三、 迷你语法分析器

13.1、题设要求

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/mini-parser

13.2、解题思路

  从左至右遍历s，如果遇到 “[” ，则表示是一个新的NestedInteger实例，需要将其入栈.如果遇到 “]” 或 “,” ，则表示是一个数字或者NestedInteger实例的结束，需要将其添加入栈顶的NestedInteger实例。最后返回栈顶的实例即可。

13.3、算法

/** * // 这是允许创建嵌列表的接口 * // 你不应该实现它，也不应该猜测它的实现 * public interface NestedInteger { * // 构造函数初始化一个空的嵌套列表 * public NestedInteger(); * * // 构造函数初始化单个整数 * public NestedInteger(int value); * * // 如果此NestedInteger包含单个整数，而不是嵌套列表，则返回True * public boolean isInteger(); * * // 如果NestedInteger包含单个整数，则返回此NestedInteger保存的单个整数 * // 如果此NestedInteger包含嵌套列表，则返回NULL * public Integer getInteger(); * * // 将此NestedInteger设置为包含单个整数 * public void setInteger(int value); * * // 设置此NestedInteger以保存嵌套列表并向其添加嵌套整数 * public void add(NestedInteger ni); * * // 如果NestedInteger包含嵌套列表，则返回此NestedInteger保存的嵌套列表 * // 如果此NestedInteger包含单个整数，则返回空列表 * public List<NestedInteger> getList(); * } */

//parseInt()函数：用于解析一个字符串，并返回一个整数
//isDigit()函数：检查参数是否为十进制数字字符

class Solution {
    
    //从左至右遍历s,如果遇到"["，则表示是一个新的NestedInteger实例,需要将其入栈.
    //如果遇到"]"或",",则表示是一个数字或者NestedInteger实例的结束，需要将其添加入栈顶的NestedInteger实例.
    //最后返回栈顶的实例即可.
    public NestedInteger deserialize(String s) {
    
        //没有"[",就一个整数,结束
        if(s.charAt(0) != '['){
    
            return new NestedInteger(Integer.parseInt(s));
        }
        //定义一个栈来存放数据
        Deque<NestedInteger> stack = new ArrayDeque<>();
        int num = 0;
        boolean negative = false;
        for (int i = 0; i < s.length(); i++) {
    
            //将字符串中的字符一一取出
            char c = s.charAt(i);
            //字符为'-',输出true
            if (c == '-') {
    
                negative = true;
            }else if (Character.isDigit(c)){
    
                //如果字符为数字，压入栈中
                num = num * 10 + c - '0';
            }else if (c == '['){
    
                //如果字符为'[',压入栈中
                stack.push(new NestedInteger());
            }else if (c == ',' || c == ']'){
    
                //如果遇到']'或',',将数字或者NestedInteger实例添加入栈顶的NestedInteger实例
                if (Character.isDigit(s.charAt(i-1))){
    
                    if (negative){
    
                        num *= -1;
                    }
                    stack.peek().add(new NestedInteger(num));
                }
                num = 0;
                negative = false;
                if (c == ']' && stack.size() > 1){
    
                    NestedInteger ni = stack.pop();
                    stack.peek().add(ni);
                }
            }
        }
        return stack.pop();
    }
}