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:
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.
这道题让我们实现一个迷你解析器用来把一个字符串解析成NestInteger类，关于这个嵌套链表类的题我们之前做过三道，
Nested List Weight Sum II，Flatten Nested List Iterator，和Nested List Weight Sum。
注: Integer.valueof(String s)是将一个包装类是将一个实际值为数字的变量先转成string型再将它转成Integer型的包装类对象(相当于转成了int的对象)这样转完的对象就具有方法和属性了。
而Integer.parseInt(String s)只是将是数字的字符串转成数字，注意他返回的是int型变量不具备方法和属性
Integer.parseInt()把String 型转换为Int型，
Integer.valueOf()把String 型转换为Integer对象。
大概知道一点了，就是说Integer.valueOf(S)是针对包装类来说的，而Integer.parseInt(s) 是针对变量而言.
括号的题想到用栈, 并不断判断符号来操作, 生成对象和更新对象, 对象的生成在字符串里通常靠双指针
心得: 字符串的题, 要学会考虑多种情况是用substring 还是charAt判断, 根据题意什么时候用substring
/**
* // 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 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;
}
一看要求就是用栈, 遍历的时候得知道遇到什么pop, 什么push, 什么时候移动左窗口指针(窗口旨在构造类, 截取元素),
遇到不同的符号怎么处理.
之所以用栈是因为题目要求和栈的特点符合: 能push, 能pop