LC.P385[迷你语法分析器]

方法一：栈

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
62
63
64
65
66
67
68
69
70
71
72
/**
 * // 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 empty list if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    // 首先需要明确，栈中，列表中，添加的都是 NestedInteger 对象
    // s = "[-2,[234, 678]]" 遍历到第一个 ']' 的时候，此时栈对应的状态为  {空，SIGN, -2, 空，SIGN, 234, 678}
    // 现在遇到了第一个 ']' ，那么我们需要将连续出栈 的 678,234 加到list，直到遇到SIGN, 也就是 list = [678,234] 然后逆序加到 空 中，使用add
    // 则此时是：{空，SIGN, -2, [234, 678]}，下一步遇到了第二个 ']'，则此时也是连续出栈，此时的 list = [[234, 678], -2]
    // 加到最开始的 空 中，
    // {[-2,[234,678]]} ; 然后 return stack.peek(); 就是 [-2,[234,678]]

    // 特殊标记，表示 '['
    private static final NestedInteger SIGN = new NestedInteger(0);

    public NestedInteger deserialize(String s) {
        Deque<NestedInteger> stack = new ArrayDeque<>();
        char[] cs = s.toCharArray();
        int n = cs.length, i = 0;
        while (i < n){
            if (cs[i] == ',') {
                ++i;
                continue; // 跳过
            }
            else if (cs[i] == '-' || (cs[i] >= '0' && cs[i] <= '9')) {
                int j = cs[i] == '-' ? i + 1 : i;
                int num = 0; // 记录当前连续的数字是多少
                while (j < n && (cs[j] >= '0' && cs[j] <= '9')) num = num * 10 + (cs[j++] - '0');
                stack.push(new NestedInteger(cs[i] == '-' ? -num : num));
                i = j;
            } else if(cs[i] == '['){
                stack.push(new NestedInteger());
                stack.push(SIGN); // 说明此时为一个'['
                ++i;
            } else { // 遇到']'
                List<NestedInteger> list = new ArrayList<>();
                while(!stack.isEmpty()){
                    NestedInteger cur = stack.pop();
                    if(cur == SIGN) break;
                    list.add(cur);
                }
                for(int j = list.size() - 1; j >= 0; --j) stack.peek().add(list.get(j)); // 逆序添加
                ++i;
            }
        }
        return stack.peek();
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$