卖萌的弱渣

I am stupid, I am hungry.

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:

Given s = “324”,

You should return a NestedInteger object which contains a single integer 324.

Example 2:

Given s = “[123,[456,[789]]]”,

Return a NestedInteger object containing a nested list with 2 elements:

1
2
3
4
5

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.

Solution

Java Solution

(Mini-Parser.java) download
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

public class Solution {
    public NestedInteger deserialize(String s) {

        if(s.isEmpty()) return null;
        // 只有一个int string -> int
        if(s.charAt(0) != '[') return new NestedInteger(Integer.valueOf(s));

        Stack<NestedInteger> stack = new Stack<NestedInteger>();
        NestedInteger cur = null;
        int l = 0;

        for(int r=0; r<s.length(); r++){
            char ch = s.charAt(r);
            // 把当前cur压入栈，并开始一个新的
            if(ch == '['){
                if(cur != null)
                    stack.push(cur);
                cur = new NestedInteger();
                l = r+1;
            }
            // 结束当前NestedInteger，弹出一个
            else if (ch==']'){
                String num = s.substring(l,r);
                if(!num.isEmpty()) cur.add(new NestedInteger(Integer.valueOf(num)));

                if(!stack.isEmpty()){
                    NestedInteger top = stack.pop();
                    top.add(cur);
                    cur = top;
                }
                l = r+1;
            }
            // 向cur中插入一个新num
            else if (ch==','){
                // 有数字
                if(s.charAt(r-1)!=']'){
                    String num = s.substring(l,r);
                    cur.add(new NestedInteger(Integer.valueOf(num)));
                }
                l = r+1;

            }

        }
        return cur;
    }
}

Python Solution

  • 遍历字符串s，记当前字符为c

  • 如果c为’-‘，则将符号变量negmul置为-1

  • 如果c为0-9，则利用变量sigma存储数字的值

  • 如果c为’[‘，则新建一个类型为列表的NestedInteger并压栈

  • 如果c为’]‘或者’,‘：

** 若sigma非空，则将sigma * negmul加入栈顶元素；

** 将栈顶元素弹出记为top；若此时栈非空，将top加入栈顶元素；否则返回top

(Mini-Parser.py) download
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
77
78
79
80
81
82
83
84

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger(object):
#    def __init__(self, value=None):
#        """
#        If value is not specified, initializes an empty list.
#        Otherwise initializes a single integer equal to value.
#        """
#
#    def isInteger(self):
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        :rtype bool
#        """
#
#    def add(self, elem):
#        """
#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
#        :rtype void
#        """
#
#    def setInteger(self, value):
#        """
#        Set this NestedInteger to hold a single integer equal to value.
#        :rtype void
#        """
#
#    def getInteger(self):
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        :rtype int
#        """
#
#    def getList(self):
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        :rtype List[NestedInteger]
#        """



class Solution(object):
    def deserialize(self, s):
        """
        :type s: str
        :rtype: NestedInteger
        """
        # 数字
        nums = None
        # 正负
        neg = 1

        stack = []
        # 只含有数字
        if s[0] != '[':
            return NestedInteger(int(s))


        for c in s:
            if c == '-':
                neg = -1
            elif c in '0123456789':
                if nums == None:
                    nums = int(c)
                else:
                    nums = 10*nums + int(c)
            elif c == '[':
                stack.append(NestedInteger())
            else:
            # "," or "]"
                if nums != None:
                    stack[-1].add(NestedInteger(nums*neg))
                    nums = None
                    neg = 1
                if c == ']':
                    top = stack.pop()
                    if stack:
                        stack[-1].add(top)
                    if not stack:
                        return top