Fork me on GitHub

Mini Parser

Posted on

This is an easy parser that can support nested list, link:https://leetcode.com/problems/mini-parser/description/

Description

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.

Implementation

We use devide and conquer to parse it.

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
85
# """
# 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
        """
        if s[0] != '[':
            return int(s)
        else:
            ret = self.parseArray(s, 0)
            return ret[0]
        
        
    def parseArray(self, s, index):
        cursor = index + 1
        length = len(s)
        ret_array = NestedInteger()
        number_str = ''
        while cursor < length:
            
            if s[cursor] == '[':
                sub_array, cursor = self.parseArray(s, cursor)
                ret_array.add(sub_array)
                
                continue
            if s[cursor] == ',':
                cursor += 1
                if number_str:
                    ret_array.add(NestedInteger(int(number_str)))
                    number_str = ''
                continue
            if s[cursor] == ']':
                if number_str:
                    ret_array.add(NestedInteger(int(number_str)))
                cursor += 1
                return ret_array, cursor
            
            ##number
            number_str += s[cursor]
            cursor += 1
        
        return ret_array, cursor
0 i1 n2 t3 e4 N5
e 1 2 3 3 4
x 2 2 3 4 4
e 3 3 3 3 4
c 4 4 4 4 4
u 5 5 5 5 5