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 digits0-9,[,-,,].

Example 1:

Given s = "324",

You should return a NestedInteger object which contains a single integer 324.

Example 2:

Given s = "[123,[456,[789]]]",

Return a NestedInteger object containing a nested list with 2 elements:

1. An integer containing value 123.
2. A nested list containing two elements:
    i.  An integer containing value 456.
    ii. A nested list with one element:
         a. An integer containing value 789.

/**
 * // 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();
 * }
 */

Solution 1: 用2个stack，一个用来存NestedInteger，另一个用来存'['和'n' (代表NestedInteger占位符)。遇到[时，压入栈；遇到]时，一直弹出NestedInteger，加入到新建的NestedInteger的list里，直到弹出栈的[；遇到数字时，压入栈，并在另一个栈压入n占位

    public NestedInteger deserialize(String s) {
        Stack<Character> stack = new Stack<>();
        Stack<NestedInteger> stack2 = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(c == '['){
                stack.push(c);
            } else if(c == ']'){
                NestedInteger curt = new NestedInteger();
                while(stack.peek() != '['){
                    stack.pop();
                    curt.add(stack2.pop());
                }
                stack.pop();
                for(int k = 0; k < curt.getList().size() / 2; k++){ //reverse
                    NestedInteger temp = curt.getList().get(k);
                    curt.getList().set(k, curt.getList().get(curt.getList().size() - 1 - k));
                    curt.getList().set(curt.getList().size() - 1 - k, temp);
                }
                stack2.push(curt);
                stack.push('n');
            } else if(c >= '0' && c <= '9'){
                int sign = 1;
                if(i - 1 >= 0 && s.charAt(i - 1) == '-'){
                    sign = -1;
                }
                int val = c - '0', j = i + 1;
                while(j < s.length() && s.charAt(j) >= '0' && s.charAt(j) <= '9'){
                    val = val * 10 + s.charAt(j) - '0';
                    j++;
                }
                i = j - 1;
                stack2.push(new NestedInteger(val * sign));
                stack.push('n');
            } 
        }
        return stack2.pop();
    }

better way: 只用一个栈

• If encounters '[', push current NestedInteger to stack and start a new one.

• If encounters ']', end current NestedInteger and pop a NestedInteger from stack to continue.

• If encounters ',', append a new number to curr NestedInteger, if this comma is not right after a brackets.
• Update index l and r, where l shall point to the start of a integer substring, while r shall points to the end+1 of substring.

public NestedInteger deserialize(String s) {
    if (s.isEmpty())
        return null;
    if (s.charAt(0) != '[') // ERROR: special case
        return new NestedInteger(Integer.valueOf(s));

    Stack<NestedInteger> stack = new Stack<>();
    NestedInteger curr = null;
    int l = 0; // l shall point to the start of a number substring; 
               // r shall point to the end+1 of a number substring
    for (int r = 0; r < s.length(); r++) {
        char ch = s.charAt(r);
        if (ch == '[') {
            if (curr != null) {
                stack.push(curr);
            }
            curr = new NestedInteger();
            l = r+1;
        } else if (ch == ']') {
            String num = s.substring(l, r);
            if (!num.isEmpty())
                curr.add(new NestedInteger(Integer.valueOf(num)));
            if (!stack.isEmpty()) {
                NestedInteger pop = stack.pop();
                pop.add(curr);
                curr = pop;
            }
            l = r+1;
        } else if (ch == ',') {
            if (s.charAt(r-1) != ']') {
                String num = s.substring(l, r);
                curr.add(new NestedInteger(Integer.valueOf(num)));
            }
            l = r+1;
        }
    }

    return curr;
}