385. Mini Parser

发表于 | 分类于

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:

1
2
3
Given s = "324",
You should return a NestedInteger object which contains a single integer 324.

Example 2:

1
2
3
4
5
6
7
8
9
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.

解法1： Stack O(N)

用一个stack来存储每一个当前的nestedInteger。
用一个variable存储指针使得他指向当前要parse的数字的开始位置。
每次看到一个,或者是]的时候就表示当前的nestedInteger结束了，所以需要把当前的数字放入nestedInteger。如果是]，如果当前的stack不为空，那么就说明这个integer属于另一个integer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * // 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();
 * }
 */
class Solution {
    public NestedInteger deserialize(String s) {
        if (s == null || s.length() == 0) {
            return new NestedInteger();
        }
        if (s.charAt(0) != '[') return new NestedInteger(Integer.parseInt(s));
        Stack<NestedInteger> stack = new Stack<>();
        int start = 1;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) =='[') {
                // start of a new NestedInteger
                stack.push(new NestedInteger());
                start = i + 1;
            } else if (s.charAt(i) == ',' || s.charAt(i) == ']') {
                if (start < i) {
                    NestedInteger top = stack.peek();
                    top.add(new NestedInteger(Integer.parseInt(s.substring(start, i))));
                }
                start = i + 1;
                if (s.charAt(i) == ']') {
                    if (stack.size() > 1) {
                        NestedInteger child = stack.pop();    
                        NestedInteger parent = stack.peek();
                        parent.add(child);
                    }
                }
            }
        }
        return stack.pop();
    }
}