leetcode Mini Parser

leetcode 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:
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.

题目地址：leetcode Mini Parser

题意：给定一个字符串，要求把它解析成NestedInteger 类型

思路：

第3个A此题怀疑前两个是出题的人自己测试的= = 本来发了discuss 想想还是只发blog吧~

本题的NestedInteger结构和341. Flatten Nested List Iterator 类似

由于没有空格，所以第一个字母不是'['的说明只有一个数字。直接返回NestedInteger(int(s))

接下来，用一个栈来维护，对于左括号[的，当前的NestedInteger 进栈，对于右括号，当前数字放入NestedInteger 栈不为空则把栈顶的NestedInteger添加当前的NestedInteger，并且出栈。

此外，注意‘-’的情况

class Solution(object):
    def deserialize(self, s):
        """
        :type s: str
        :rtype: NestedInteger
        """
        if s[0] != '[': return NestedInteger(int(s))
        stack = []
        n = len(s)
        cur = minus = num = None
        for i in xrange(n):
            if s[i] == '[':
                if cur is not None:
                    stack.append(cur)
                cur = NestedInteger()
            elif s[i] in [']', ',']:
                if num is not None:
                    if minus: num *= -1
                    cur.add(num)
                if s[i] == ']' and stack:
                    stack[-1].add(cur)
                    cur = stack.pop()
                minus = num = None
            elif s[i] == '-':
                minus = True
            else:
                if num is None: num = 0
                num = num * 10 + ord(s[i]) - 48
        return cur

本题是leetcode 385 Mini Parser 的题解

更多题解可以查看：https://www.hrwhisper.me/leetcode-algorithm-solution/