题目

• 概述：给定一个用字符串表示的整数的嵌套列表，列表中的每个元素只能是整数或者整数嵌套列表，实现一个解析它的语法分析器

• 输入：字符串表示的整数的嵌套列表

  字符串非空

  字符串不包含空格

  字符串只包含数字0-9，[，]，,，-

  示例1：“324”

  示例2：“[123,[456,[789]]]”

• 输出：NestedInteger对象，详见代码注释

• 出处：https://leetcode-cn.com/problems/mini-parser/

思路

• 由于是嵌套的，所以考虑用栈实现

• 遍历字符串:

  1. '[' => 创建NestedInteger对象放入栈中
  2. 数字或'-' => 拼接到数字字符串上
  3. ',' => 若数字字符串不为空（"[[],[]]"），将数字字符串转换为数字并加入到栈顶的NestedInteger对象中，将数字字符串清空
  4. ']' => 若数字字符串不为空，则执行3，然后将栈顶元素出栈加入到出栈后的栈顶元素中(若没有栈顶元素则直接返回该答案)

• 若最后数字字符串不为空（"123"），则创建只带数字的NestedInteger对象并返回

代码

/**
 * // 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 null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    public NestedInteger deserialize(String s) {
        LinkedList<NestedInteger> stack = new LinkedList<>();
        StringBuilder numberStr = new StringBuilder();
        NestedInteger top;
        
        for (char c : s.toCharArray()) {
            switch (c) {
                case '[':
                    stack.push(new NestedInteger());
                    break;
                case ',':
                    if (numberStr.length() > 0) {
                        stack.peek().add(new NestedInteger(Integer.parseInt(numberStr.toString())));
                    numberStr = new StringBuilder();
                    }
                    break;
                case ']':
                    if (numberStr.length() > 0) {
                        stack.peek().add(new NestedInteger(Integer.parseInt(numberStr.toString())));
                    numberStr = new StringBuilder();
                    }
                    
                    top = stack.pop();
                    if (stack.isEmpty()) {
                        return top;
                    } else {
                        stack.peek().add(top);
                    }
                    break;
                default:
                    numberStr.append(c);
                    break;
            }
        }
        
        if (numberStr.length() > 0) {
            return new NestedInteger(Integer.parseInt(numberStr.toString()));
        } else {
            return stack.peek();
        }
    }
}