​力扣解法汇总358-迷你语法分析器

目录链接：

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目：

https://github.com/September26/java-algorithms

原题链接：

力扣

描述：

给定一个字符串 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

* 解题思路：
* 这种对称的结构最适合使用栈的思想来接题目。
* 由于本题当中，对象有两种形式，数组和数字形式。所以我们先生成对象加入到集合当中，后续遍历过程中再决定其类型。
* 栈的话用来装载一层一层的对象，读到[则说明增加增加一层级。读到]则介绍一层级。
* 针对字符从前向后遍历，每个字符分为以下几种情况：
* 1.字符串为'['时，则说明当前对象是一个数组的形式，则生成一个对象加入到数组中（此时还未确定时数组还是数字形式）。
* 2.字符串为']'时，则说明当前数组的循环结束，则从栈中pop出最上层节点。
* 3.字符串为'.'时，则说明应该读取下一组对象。
* 4.字符串为数字时，则记录一下，start++。除此之外，除了数字类型，都会触发字符串结束判断，生成一个数字类型的对象加入到最上层的栈对象中。

代码：

public class Solution385 {


    public NestedInteger deserialize(String s) {
        Stack<NestedInteger> stack = new Stack<>();
        NestedInteger root = new NestedInteger();
        stack.add(root);
        StringBuilder builder = new StringBuilder();

        int start = 0;
        char[] chars = s.toCharArray();
        while (true) {
            if (start == chars.length) {
                addValue(builder, stack);
                break;
            }
            char aChar = chars[start];
            if (aChar == '[') {
                NestedInteger value = new NestedInteger();
                stack.peek().getList().add(value);
                stack.add(value);
                start++;
                continue;
            }
            if (aChar == ']') {
                addValue(builder, stack);
                stack.pop();
                start++;
                continue;
            }
            if (aChar == ',') {
                addValue(builder, stack);
                start++;
                continue;
            }
            builder.append(aChar);
            start++;
        }
        NestedInteger result = stack.pop().getList().get(0);
        return result;
    }

    private void addValue(StringBuilder builder, Stack<NestedInteger> stack) {
        if (builder.length() == 0) {
            return;
        }
        NestedInteger value = new NestedInteger(Integer.parseInt(builder.toString()));
        stack.peek().add(value);
        builder.setLength(0);
    }


    class NestedInteger {
        Integer mValue;
        List<NestedInteger> list = new ArrayList<>();

        public NestedInteger() {
        }

        public NestedInteger(int value) {
            this.mValue = value;
        }


        public boolean isInteger() {
            return mValue != null;
        }


        public Integer getInteger() {
            return mValue;
        }


        public void setInteger(Integer value) {
            this.mValue = value;
            this.list = null;
        }


        public void add(NestedInteger ni) {
            list.add(ni);
        }


        public List<NestedInteger> getList() {
            return list;
        }
    }

}