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
遇到’[‘字符肯定是要產(chǎn)生一個(gè)新的 NestedInteger 對(duì)象的。
遇到’]’字符則表明上一個(gè)元素可以結(jié)束了疚漆，此時(shí)要處理這里面的整型字符串扫倡，將其解析成int值再傳給當(dāng)前的NestedInteger對(duì)象坑夯。并且呢，由于當(dāng)前元素已經(jīng)結(jié)束解析羊初，還需要將它傳給它的父NestedInteger籽慢。
遇到’,’字符要分情況了，如果它的前一個(gè)字符是’]’則表明在步驟2種已經(jīng)做了處理了蜂桶，否則的話說(shuō)明之前的整型字符串還沒有解析。
如果遇到了0到9還有－也切，則暫時(shí)不作處理扑媚，將其拼接到一個(gè)StringBuilder里面。
我們這里再來(lái)拿一個(gè)字符串來(lái)討論看看雷恃，對(duì)于字符串”[-1,[123],[[3]]]”
首先遇到’[‘產(chǎn)生一個(gè)NestedInteger疆股，對(duì)應(yīng)著最外層的NestedInteger， 記作NI1倒槐，并賦值給curNi(NI1)旬痹；
接著向后遍歷，直到遇到了第一個(gè)’,’讨越，此時(shí)要為前面的整型值’-1’實(shí)例化一個(gè)NestedInteger對(duì)象两残，并插入到最外層的curNi(NI1)；
繼續(xù)向后遍歷把跨，遇到第二個(gè)’[‘人弓，先將curNi(NI1)壓入stack中，再實(shí)例化一個(gè)新的NestedInteger對(duì)象着逐，記作NI2崔赌，且令賦值給curNi(NI2)；
向后遍歷耸别，遇到第二個(gè)’[‘所對(duì)應(yīng)的’]’健芭，為前面的整型值’123’實(shí)例化一個(gè)NestedInteger對(duì)象，add進(jìn)curNI(NI2)中秀姐。再?gòu)棾鰏tack中的NI1對(duì)象慈迈，將curNI(NI2)add到NI中，再令curNi ＝ NI1省有，注意此時(shí)stack中已空痒留；
繼續(xù)，遇到第二個(gè)’,’但是發(fā)現(xiàn)它的前一個(gè)字符是’]’锥咸，不作處理狭瞎；
繼續(xù)遍歷，遇到第三個(gè)’[‘搏予，先將curNI(NI1)壓入stack中熊锭。再實(shí)例化一個(gè)新的NestedInteger對(duì)象，記作NI3雪侥，令curNI = NI3碗殷；
繼續(xù)遍歷，遇到第四個(gè)’[‘速缨，先將curNI(NI3)壓入stack中锌妻。再實(shí)例化一個(gè)新的NestedInteger對(duì)象，記作NI4旬牲，令curNI = NI4仿粹；
繼續(xù)遍歷搁吓，遇到第四個(gè)’[‘所對(duì)應(yīng)的’]’，為’3’實(shí)例化一個(gè)NestedInteger對(duì)象吭历，插入到curNI(NI4)中堕仔。從stack中彈出NI3，將curNI(NI4)插入到NI3中晌区，且令curNI = NI3摩骨；
繼續(xù)遍歷，遇到第三個(gè)’[‘所對(duì)應(yīng)的’]’朗若，前面沒有未處理的整型字符串恼五。此時(shí)stack里面還有一個(gè)NI1，彈出NI1哭懈，將curNI(NI3)add給NI1灾馒，且令curNI = NI1；
到了最后一個(gè)’]’银伟，也對(duì)應(yīng)了第一個(gè)’]’你虹，此時(shí)stack為空，且沒有未處理的字符串了彤避。此時(shí)傅物，curNI就對(duì)應(yīng)了最外層的那個(gè)NestedInteger，結(jié)束琉预。
