Question

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

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:

An integer containing value 123.

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.

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();
 * }
 */
public class Solution {
    public NestedInteger deserialize(String s) {
        if (s.isEmpty()) return null;
        if (s.charAt(0) != '[') return new NestedInteger(Integer.valueOf(s));
        
        Stack<NestedInteger> stack = new Stack<>();
        NestedInteger curr = null;
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '[') {
                if (curr != null) stack.push(curr);
                curr = new NestedInteger();
            } else if (c == ']') {
                if (sb.length() > 0) {
                    curr.add(new NestedInteger(Integer.valueOf(sb.toString())));
                    sb.delete(0, sb.length());
                }
                if (!stack.isEmpty()) {
                    NestedInteger ni = stack.pop();
                    ni.add(curr);
                    curr = ni;
                }
            } else if (c == ',') {
                if (s.charAt(i - 1) != ']') {
                    curr.add(new NestedInteger(Integer.valueOf(sb.toString())));
                    sb.delete(0, sb.length());
                }
            } else {
                sb.append(c);
            }
        }
        return curr;
    }
}

Solution

http://m.blog.csdn.net/article/details?id=52259424

遇到’[‘字符肯定是要产生一个新的 NestedInteger 对象的。
遇到’]’字符则表明上一个元素可以结束了，此时要处理这里面的整型字符串，将其解析成int值再传给当前的NestedInteger对象。并且呢，由于当前元素已经结束解析，还需要将它传给它的父NestedInteger。
遇到’,’字符要分情况了，如果它的前一个字符是’]’则表明在步骤2种已经做了处理了，否则的话说明之前的整型字符串还没有解析。
如果遇到了0到9还有－，则暂时不作处理，将其拼接到一个StringBuilder里面。

我们这里再来拿一个字符串来讨论看看，对于字符串”[-1,[123],[[3]]]”
首先遇到’[‘产生一个NestedInteger，对应着最外层的NestedInteger，记作NI1，并赋值给curNi(NI1)；
接着向后遍历，直到遇到了第一个’,’，此时要为前面的整型值’-1’实例化一个NestedInteger对象，并插入到最外层的curNi(NI1)；
继续向后遍历，遇到第二个’[‘，先将curNi(NI1)压入stack中，再实例化一个新的NestedInteger对象，记作NI2，且令赋值给curNi(NI2)；
向后遍历，遇到第二个’[‘所对应的’]’，为前面的整型值’123’实例化一个NestedInteger对象，add进curNI(NI2)中。再弹出stack中的NI1对象，将curNI(NI2)add到NI中，再令curNi ＝ NI1，注意此时stack中已空；
继续，遇到第二个’,’但是发现它的前一个字符是’]’，不作处理；
继续遍历，遇到第三个’[‘，先将curNI(NI1)压入stack中。再实例化一个新的NestedInteger对象，记作NI3，令curNI = NI3；
继续遍历，遇到第四个’[‘，先将curNI(NI3)压入stack中。再实例化一个新的NestedInteger对象，记作NI4，令curNI = NI4；
继续遍历，遇到第四个’[‘所对应的’]’，为’3’实例化一个NestedInteger对象，插入到curNI(NI4)中。从stack中弹出NI3，将curNI(NI4)插入到NI3中，且令curNI = NI3；
继续遍历，遇到第三个’[‘所对应的’]’，前面没有未处理的整型字符串。此时stack里面还有一个NI1，弹出NI1，将curNI(NI3)add给NI1，且令curNI = NI1；
到了最后一个’]’，也对应了第一个’]’，此时stack为空，且没有未处理的字符串了。此时，curNI就对应了最外层的那个NestedInteger，结束。