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)

341 Flatten Nested List Iterator

394 Decode String

Last modified 2yr ago

Copy link

Contents

385. Mini Parser

1. Question

2. Implementation

3. Time & Space Complexity

385. Mini Parser​

1. Question

2. Implementation

3. Time & Space Complexity

385. Mini Parser