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，结束。
