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

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.

Solution： Stack

Example：[12, 45, [67, 89], [34, 51, [451, 251, 534]], 35]
思路： 遍历将遇到的num加到cur list中，每当碰到 '[' ，将cur list push到stack中，并new一个cur_list继续遍历。当碰到']'时，pop一个list作为prev_list，将cur_list add进 prev_list中，prev_list作为cur_list继续

Time Complexity: O(nm) Space Complexity: O(nm)
n 个 str (nested), m 长度

Solution Code：

class Solution {
    public NestedInteger deserialize(String s) {
        if (s == null || s.isEmpty())
            return null;
        
        if (s.charAt(0) != '[') // ERROR: special case
            return new NestedInteger(Integer.valueOf(s));
        
        Deque<NestedInteger> stack = new ArrayDeque<>();
        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);
                // add current num to cur list
                if (!num.isEmpty()) curr.add(new NestedInteger(Integer.valueOf(num)));
                // get previous list and 
                if (!stack.isEmpty()) {
                    NestedInteger pop = stack.pop();
                    pop.add(curr);
                    curr = pop;
                }
                l = r + 1;
            } else if (ch == ',') {
                if (s.charAt(r - 1) != ']') {  //except for the ',' after ']', becuase that has already been taken care of when ch == ']'
                    String num = s.substring(l, r);
                    curr.add(new NestedInteger(Integer.valueOf(num)));
                }
                l = r+1;
            }
        }

        return curr;
    }
}