Mini Parser

https://leetcode.com/problems/mini-parser/description/

Given a nested list of integers represented as a string, implement a parser to deserialize it.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Note:You may assume that the string is well-formed:

• String is non-empty.

• String does not contain white spaces.

• String contains only digits

Thoughts

和上一道Decode String以及Basic Calculator思路一致, 也是让res存储当前括号内的内容, 遇到'['就把目前内容Push进栈, res清空. 遇到']'则把栈内 属于 更外层的']' 的内容从栈内抛出和当前res合并成对应着更外层括号的内容. 那么怎么样做能只抛属于某个括号的内容呢? 我们在遇到'['push进栈时顺便push进一个Null当作分隔符就好了.

Code

/**
 * // 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) {
        if (s.charAt(0) != '[') // ERROR: special case
        return new NestedInteger(Integer.valueOf(s));
        Stack<NestedInteger> stack = new Stack<>();
        LinkedList<NestedInteger> res = new LinkedList<>();
        int sign = 1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int end = i + 1;
                while (Character.isDigit(s.charAt(end))) {
                    end++;
                }
                res.add(new NestedInteger(sign * Integer.parseInt(s.substring(i, end))));
                sign = 1;
                i = end - 1;
            } else if (c == ',') {
                continue;
            } else if (c == '[') {
                stack.push(null);
                for (NestedInteger ni : res) {
                    stack.push(ni);
                }
                res.clear();
            } else if (c == ']') {
                NestedInteger ni = new NestedInteger();
                List list = ni.getList();

                for (NestedInteger n : res) {
                    list.add(n);
                }
                res.clear();
                while (!stack.isEmpty() && stack.peek() != null) {
                    res.addFirst(stack.pop());
                }
                if (!stack.isEmpty() && stack.peek() == null) {
                    stack.pop();
                }
                res.add(ni);
            } else if (c == '-') {
                sign = -1;
            }         
        }

        return res.get(0);
    }
}

Analysis

Errors: 1. 别忘了还有负数, 需要一个sign 时空复杂度都是O(N).