Mini Parser: Stack-Based Nested List Deserializer

Mini Parser is LeetCode 385, rated Medium. You are given a string like "[123,[456,[789]]]" and you need to parse it into a NestedInteger data structure where each element is either a plain integer or a list of other NestedIntegers.

If you have ever written a JSON parser or dealt with recursive grammars, this will feel familiar. The trick is that you do not need actual recursion. A stack handles the nesting naturally.

The key insight

Every time you see a [, you are entering a new nested list. Every time you see a ], you are closing one. A stack lets you track which list you are currently building. When a list closes, you pop it and tuck it inside the list that sits one level above.

The characters between brackets are either digits (possibly with a leading -) that form numbers, or commas that separate elements. Commas and closing brackets both tell you "the current number is done, finalize it."

The approach

Walk through the string character by character and maintain two things: a stack of NestedInteger lists, and a temporary string num to accumulate digit characters.

1. [ - Push a new empty NestedInteger list onto the stack. You are starting a new nesting level.
2. Digit or - - Append to num. You are in the middle of reading a number.
3. , - If num is non-empty, convert it to an integer, wrap it in a NestedInteger, and add it to the list on top of the stack. Reset num.
4. ] - If num is non-empty, finalize the number the same way as with a comma. Then pop the top list off the stack. If the stack is not empty, add the popped list to the new top. If the stack is empty, you are done - return the popped list.

There is one edge case at the very start: if the string does not begin with [, the entire input is a single integer. Return it directly.

The code

class Solution:
    def deserialize(self, s: str) -> NestedInteger:
        if s[0] != '[':
            return NestedInteger(int(s))
        stack = []
        num = ""
        for ch in s:
            if ch == '[':
                stack.append(NestedInteger())
            elif ch == ']':
                if num:
                    stack[-1].add(NestedInteger(int(num)))
                    num = ""
                top = stack.pop()
                if stack:
                    stack[-1].add(top)
                else:
                    return top
            elif ch == ',':
                if num:
                    stack[-1].add(NestedInteger(int(num)))
                    num = ""
            else:
                num += ch
        return stack[0]

Complexity

Time: O(n). You scan each character exactly once. Every push, pop, and add operation is O(1), so total work scales linearly with the length of the input string.

Space: O(n). The stack depth equals the maximum nesting level of the input. In the worst case (something like [[[[...]]]]), that could approach n/2. The num accumulator is at most O(n) for a very long number. Both are O(n).

Building blocks

Stack-based nesting

The core pattern here is using a stack to handle recursive structure without actual recursion. Each open delimiter pushes a new context. Each close delimiter pops a context and merges it into the parent.

This is the same pattern you see in:

• Basic Calculator - parentheses push and pop evaluation contexts
• Evaluate Reverse Polish Notation - the stack holds intermediate results waiting for operators
• Decode String (3[a2[bc]]) - brackets push and pop string-building contexts
• Valid Parentheses - the simplest version, where you just push openers and pop on closers

Once you recognize "nested structure processed left to right," reach for a stack.

Number accumulation

The other small pattern is building a number character by character. You collect digits into a string and finalize the number when you hit a non-digit delimiter. This shows up in any parsing problem: string-to-integer, calculator evaluation, IP address restoration. The key is knowing when to flush the accumulator.

Edge cases

• Single integer. "324" has no brackets. The very first check (s[0] != '[') catches this and returns immediately.
• Negative numbers. "[-1]" is valid. The - character falls into the else branch and gets appended to num, so int(num) correctly handles it.
• Empty nested list. "[[]]" is valid. The inner ] pops an empty NestedInteger list and adds it to the outer one. No number is finalized because num is empty.
• Deeply nested single values. "[[[5]]]" works fine. Each ] pops a list and nests it into the one below.
• Multiple commas in a row never happen. The problem guarantees valid input, so you do not need to handle "[1,,2]".

From understanding to recall

Mini Parser is a clean example of the stack-based nesting pattern. The code is short - about 15 lines - but the details matter. When do you flush num? On commas and closing brackets. What do you do after popping? Check if the stack is empty. What about the single-integer edge case? Handle it before the loop.

These are the kinds of things that slip away after a week. You understand the algorithm right now, but reproducing it from memory under interview pressure is a different skill. Spaced repetition locks in those decision points. You write the parser from scratch at increasing intervals until the flow is automatic: check for bare integer, loop through characters, push on [, flush and pop on ], flush on ,, accumulate otherwise. After a few cycles, the code writes itself.

Related posts

• Basic Calculator - stack-based expression parsing with parentheses and operators
• Evaluate Reverse Polish Notation - stack for structured evaluation of postfix expressions
• Flatten Nested List Iterator - working with nested list structures from the other direction