LeetCode 385: Mini Parser

Problem Restatement

We are given a string s.

The string represents either:

1. A single integer
2. A nested list of integers

Examples:

"324"
"[123,[456,[789]]]"
"[-1,[2,-3],4]"

We need to parse this string and return a NestedInteger object.

The NestedInteger class is already provided by LeetCode. We only need to implement:

deserialize(s)

Input and Output

Example function shape:

def deserialize(s: str) -> NestedInteger:
    ...

Examples

Example 1:

s = "324"

This is a single integer, so the result should represent:

324

Example 2:

s = "[123,[456,[789]]]"

This represents a nested list:

[
    123,
    [
        456,
        [
            789
        ]
    ]
]

Example 3:

s = "[-1,[2,-3],4]"

This represents:

[
    -1,
    [
        2,
        -3
    ],
    4
]

First Thought: Recursive Parsing

Because the structure is nested, recursion feels natural.

When we see [, we parse a list.

When we see a number, we parse an integer.

When we see ], the current list ends.

This is a valid approach, but it requires careful index handling. We need to pass the current position through recursive calls.

A stack solution is often easier to write and debug.

Key Insight

The string has clear structural tokens:

A stack can track the currently open lists.

When we see [, we create a new NestedInteger list and push it.

When we finish a number, we add it to the current top list.

When we see ], the current list is complete. We pop it and add it to the previous list.

Algorithm

Handle the special case first.

If the string does not start with [, it is a single integer:

return NestedInteger(int(s))

Otherwise:

1. Create an empty stack.
2. Use index i to scan the string.
3. If s[i] == "[", create a new empty NestedInteger and push it.
4. If s[i] == "]", pop the completed list.
   • If the stack still has a parent list, add the completed list to the parent.
   • Otherwise, this completed list is the final answer.
5. If s[i] == ",", skip it.
6. Otherwise, parse a full integer and add it to the current top list.

The main parsing detail is reading multi-digit and negative numbers.

For example, when we see:

-123

we must read the whole token, not only - or 1.

Correctness

The stack stores the chain of lists that are currently open.

When the parser reads [, a new list begins. Pushing a new NestedInteger onto the stack correctly makes it the current active list.

When the parser reads an integer, that integer belongs to the innermost currently open list. The top of the stack is exactly that list, so adding the integer there is correct.

When the parser reads ], the current list is complete. Popping the top list gives exactly the list whose closing bracket was just read. If there is a parent list on the stack, the completed list is an element of that parent, so adding it to the new top is correct. If there is no parent, the completed list is the full parsed result.

Commas only separate elements, so skipping them does not change the parsed structure.

Since every character is processed according to its syntactic role, and every nested list is attached to its parent when its closing bracket appears, the returned object matches the serialized input.

Complexity

Let n = len(s).

The returned NestedInteger object itself stores all parsed values.

Implementation

class Solution:
    def deserialize(self, s: str) -> NestedInteger:
        if s[0] != "[":
            return NestedInteger(int(s))

        stack = []
        i = 0

        while i < len(s):
            ch = s[i]

            if ch == "[":
                stack.append(NestedInteger())
                i += 1

            elif ch == "]":
                completed = stack.pop()

                if not stack:
                    return completed

                stack[-1].add(completed)
                i += 1

            elif ch == ",":
                i += 1

            else:
                start = i

                if s[i] == "-":
                    i += 1

                while i < len(s) and s[i].isdigit():
                    i += 1

                value = int(s[start:i])
                stack[-1].add(NestedInteger(value))

        return NestedInteger()

Code Explanation

First, handle the plain integer case:

if s[0] != "[":
    return NestedInteger(int(s))

This covers inputs like:

"324"
"-10"

For nested lists, we use a stack:

stack = []

When we see an opening bracket, we start a new list:

if ch == "[":
    stack.append(NestedInteger())

When we see a closing bracket, the current list is complete:

completed = stack.pop()

If the stack is empty after popping, this completed list is the whole answer:

if not stack:
    return completed

Otherwise, add it to its parent list:

stack[-1].add(completed)

Commas are separators, so we skip them:

elif ch == ",":
    i += 1

For a number, we record its start index:

start = i

If the number is negative, we move past the minus sign:

if s[i] == "-":
    i += 1

Then we consume all digits:

while i < len(s) and s[i].isdigit():
    i += 1

Now s[start:i] is the full integer token.

We convert it and add it to the current list:

value = int(s[start:i])
stack[-1].add(NestedInteger(value))

Testing

LeetCode provides NestedInteger, but for local testing we can create a small mock version.

class NestedInteger:
    def __init__(self, value=None):
        if value is None:
            self.value = None
            self.items = []
        else:
            self.value = value
            self.items = None

    def isInteger(self):
        return self.items is None

    def add(self, elem):
        if self.items is None:
            self.items = []
            self.value = None
        self.items.append(elem)

    def setInteger(self, value):
        self.value = value
        self.items = None

    def getInteger(self):
        return self.value

    def getList(self):
        return self.items

    def to_python(self):
        if self.isInteger():
            return self.value
        return [item.to_python() for item in self.items]

def test_solution():
    s = Solution()

    assert s.deserialize("324").to_python() == 324
    assert s.deserialize("-10").to_python() == -10
    assert s.deserialize("[123,[456,[789]]]").to_python() == [123, [456, [789]]]
    assert s.deserialize("[-1,[2,-3],4]").to_python() == [-1, [2, -3], 4]
    assert s.deserialize("[]").to_python() == []
    assert s.deserialize("[[]]").to_python() == [[]]
    assert s.deserialize("[0,[10,-20],30]").to_python() == [0, [10, -20], 30]

    print("all tests passed")

test_solution()

Test meaning: