385. Mini Parser

  • 30.6%

https://leetcode.com/problems/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, [, - ,, ].
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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. 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.

python

Python using eval:

1
2
3
4
5
6
7
8
9
def deserialize(self, s):
def nestedInteger(x):
if isinstance(x, int):
return NestedInteger(x)
lst = NestedInteger()
for y in x:
lst.add(nestedInteger(y))
return lst
return nestedInteger(eval(s))

Python one-liner

1
2
def deserialize(self, s):
return NestedInteger(s) if isinstance(s, int) else reduce(lambda a, x: a.add(self.deserialize(x)) or a, s, NestedInteger()) if isinstance(s, list) else self.deserialize(eval(s))

Python Golf (136 bytes or 31 bytes)

1
class Solution:deserialize=d=lambda S,s,N=NestedInteger:s<[]and N(s)or s<''and reduce(lambda a,x:a.add(S.d(x))or a,s,N())or S.d(eval(s))

Or abusing how the judge judges (yes, this gets accepted):

1
class Solution:deserialize=eval

Python parsing char by char

Here I turned the input string into a list with sentinel for convenience.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def deserialize(self, s):
def nestedInteger():
num = ''
while s[-1] in '1234567890-':
num += s.pop()
if num:
return NestedInteger(int(num))
s.pop()
lst = NestedInteger()
while s[-1] != ']':
lst.add(nestedInteger())
if s[-1] == ',':
s.pop()
s.pop()
return lst
s = list(' ' + s[::-1])
return nestedInteger()

cpp

C++ using istringstream

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
NestedInteger deserialize(string s) {
istringstream in(s);
return deserialize(in);
}
private:
NestedInteger deserialize(istringstream &in) {
int number;
if (in >> number)
return NestedInteger(number);
in.clear();
in.get();
NestedInteger list;
while (in.peek() != ']') {
list.add(deserialize(in));
if (in.peek() == ',')
in.get();
}
in.get();
return list;
}
};
谢谢你,可爱的朋友。