385. 迷你语法分析器 - 《算法》

题目
思路
代码
- 栈

题目

给定一个字符串 s 表示一个整数嵌套列表，实现一个解析它的语法分析器并返回解析的结果 NestedInteger 。

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

示例 1：

输入：s = “324”,
输出：324
解释：你应该返回一个 NestedInteger 对象，其中只包含整数值 324。

示例 2：

输入：s = “[123,[456,[789]]]”,
输出：[123,[456,[789]]]
解释：返回一个 NestedInteger 对象包含一个有两个元素的嵌套列表：

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

提示：

1 <= s.length <= 5 * 10^4
s 由数字、方括号 “[]”、负号 ‘-‘ 、逗号 ‘,’组成
用例保证 s 是可解析的 NestedInteger
输入中的所有值的范围是 [-10^6, 10^6]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/mini-parser
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

最近写过最磕磕绊绊的一个题了…递归还是自己写不出来，栈的话还好写一点，不过也有一些细节需要注意。

如果第一个字符不是左括号，那么说明只有一个数字，直接使用该数字初始化NestedInteger的实例，返回这个实例。否则进行下面循环，依次判断每个字符。

如果遇到’[‘，说明新开始了一个nested list，声明一个新的NestedInteger入栈。

如果遇到’-‘，标记接下来的数字为负数。

如果遇到数字字符，更新数字num。直到遇到’,’或者’]’(注意是数字后面的’,’或者’]’)，说明当前数字结束，将num加入栈顶的NestedInteger实例。然后将num置0，负数标记重置，因为这两个变量是for循环外的变量。另外，当前字符如果为’]’并且栈中元素多于一个，那么需要将栈顶的实例出栈并加入次顶的实例。

代码

栈

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return empty list if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    public NestedInteger deserialize(String s) {
        // 说明只有一个数字
        if (s.charAt(0) != '[') {
            return new NestedInteger(Integer.parseInt(s));
        }
        int n = s.length();
        Deque<NestedInteger> stack = new ArrayDeque<>();
        // num和negative为循环外变量，比较方便编码，内部不用再写循环以及讨论边界
        int num = 0;
        boolean negative = false;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '[') {
                stack.push(new NestedInteger());
            } else if (c == '-') {
                negative = true;
            } else if (Character.isDigit(c)) {
                num = 10 * num + c - '0';
            } else if (c == ',' || c == ']') {
                // 前面是数字才将num添加到当前层list
                if (Character.isDigit(s.charAt(i - 1))) {
                    if (negative) {
                        num *= -1;
                    }
                    stack.peek().add(new NestedInteger(num));
                }
                // 一个数字结束就将num和negative重置
                num = 0;
                negative = false;
                // 里面嵌套的list结束了，添加到它的父list中，
                if (c == ']' && stack.size() > 1) {
                    // 不能合并起来写
                    NestedInteger ni = stack.pop();
                    stack.peek().add(ni);
                }
            }
        }
        return stack.pop();
    }
}