leetcode-mini-parser

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/mini-parser/

　　实现一个反序列化的程序，反序列化一个含有数字及其嵌套的list。

题目分析

　　细节实现题，我用了递归，注意找匹配左[的右 ]用到了栈。

代码

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
73
74
75
76
/**
 * // 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 class Solution {
    public NestedInteger deserialize(String s) {
        char[] c = s.toCharArray();
        int len = c.length;
        // "[123,[456,[789]]]"
        NestedInteger ni = new NestedInteger();
        if (c[0] == '[') { // 不是数字
            if (len == 2) { // 空的，"[]"
                return ni;
            }
            int i = 1;
            while (i < len) {
                int start = i;
                if (c[i] != '[') { // 直接是数字
                    for (; i < len; i++) {
                        if (c[i] == ',' || c[i] == ']') {
                            break;
                        }
                    }
                    NestedInteger tmp = new NestedInteger();
                    tmp.setInteger(Integer.valueOf(s.substring(start, i)));
                    ni.add(tmp);
                    i++;
                } else {
                    Stack<Character> stack = new Stack<Character>(); //借助栈找其匹配的
                    i++;
                    while (i < len) {
                        if (c[i] == '[') {
                            stack.push(c[i]);
                        } else if (c[i] == ']') {
                            if (!stack.empty()) {
                                stack.pop();
                            } else {
                                ni.add(deserialize(s.substring(start, i + 1))); // 递归
                                i += 2;
                                break;
                            }
                        }
                        i++;
                    }
                }
            }
        } else { // 数字
            ni.setInteger(Integer.valueOf(s));
        }
        return ni;
    }
}