385 Mini Parser

385. Mini Parser

1. 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 digits0-9,[,-,,].
Example 1:
1
Given s = "324",
2
3
You should return a NestedInteger object which contains a single integer 324.
Copied!
Example 2:
1
Given s = "[123,[456,[789]]]",
2
3
Return a NestedInteger object containing a nested list with 2 elements:
4
5
1. An integer containing value 123.
6
2. A nested list containing two elements:
7
i. An integer containing value 456.
8
ii. A nested list with one element:
9
a. An integer containing value 789.
Copied!

2. Implementation

(1) Stack
1
/**
2
* // This is the interface that allows for creating nested lists.
3
* // You should not implement it, or speculate about its implementation
4
* public interface NestedInteger {
5
* // Constructor initializes an empty nested list.
6
* public NestedInteger();
7
*
8
* // Constructor initializes a single integer.
9
* public NestedInteger(int value);
10
*
11
* // @return true if this NestedInteger holds a single integer, rather than a nested list.
12
* public boolean isInteger();
13
*
14
* // @return the single integer that this NestedInteger holds, if it holds a single integer
15
* // Return null if this NestedInteger holds a nested list
16
* public Integer getInteger();
17
*
18
* // Set this NestedInteger to hold a single integer.
19
* public void setInteger(int value);
20
*
21
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
22
* public void add(NestedInteger ni);
23
*
24
* // @return the nested list that this NestedInteger holds, if it holds a nested list
25
* // Return null if this NestedInteger holds a single integer
26
* public List<NestedInteger> getList();
27
* }
28
*/
29
class Solution {
30
public NestedInteger deserialize(String s) {
31
if (s.charAt(0) != '[') {
32
return new NestedInteger(Integer.parseInt(s));
33
}
34
35
Stack<NestedInteger> stack = new Stack<>();
36
37
int n = s.length();
38
39
NestedInteger res = null;
40
NestedInteger curNI = new NestedInteger();
41
int i = 0;
42
while (i < n) {
43
char c = s.charAt(i);
44
if (c == '[') {
45
curNI = new NestedInteger();
46
if (!stack.isEmpty()) {
47
stack.peek().add(curNI);
48
}
49
stack.push(curNI);
50
}
51
else if (c == ']') {
52
res = stack.pop();
53
}
54
else if (c == '-' || Character.isDigit(c)) {
55
int sign = 1;
56
int val = 0;
57
if (c == '-') {
58
sign = -1;
59
}
60
else {
61
val = c - '0';
62
}
63
// skip current position
64
++i;
65
66
while (i < n && Character.isDigit(s.charAt(i))) {
67
val = 10 * val + s.charAt(i) - '0';
68
++i;
69
}
70
// return back last position, because we will increase i in the end
71
--i;
72
73
curNI = new NestedInteger(sign * val);
74
if (!stack.isEmpty()) {
75
stack.peek().add(curNI);
76
}
77
}
78
++i;
79
}
80
return res;
81
}
82
}
Copied!

3. Time & Space Complexity

时间复杂度O(n), 空间复杂度O(n)