# 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:

```python
"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:

```python
deserialize(s)
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | A serialized string `s` |
| Output | A `NestedInteger` object |
| Integer format | May be positive or negative |
| List format | Uses square brackets |
| Nesting | Lists may contain integers or more lists |

Example function shape:

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

## Examples

Example 1:

```python
s = "324"
```

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

```python
324
```

Example 2:

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

This represents a nested list:

```python
[
    123,
    [
        456,
        [
            789
        ]
    ]
]
```

Example 3:

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

This represents:

```python
[
    -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:

| Token | Meaning |
|---|---|
| `[` | Start a new nested list |
| `]` | Finish the current nested list |
| `,` | Separator between elements |
| digit or `-` | Part of an integer |

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:

```python
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:

```python
-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)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each character is scanned once |
| Space | `O(d)` | The stack stores currently open lists, where `d` is nesting depth |

The returned `NestedInteger` object itself stores all parsed values.

## Implementation

```python
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:

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

This covers inputs like:

```python
"324"
"-10"
```

For nested lists, we use a stack:

```python
stack = []
```

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

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

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

```python
completed = stack.pop()
```

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

```python
if not stack:
    return completed
```

Otherwise, add it to its parent list:

```python
stack[-1].add(completed)
```

Commas are separators, so we skip them:

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

For a number, we record its start index:

```python
start = i
```

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

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

Then we consume all digits:

```python
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:

```python
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.

```python
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:

| Test | Why |
|---|---|
| `"324"` | Single positive integer |
| `"-10"` | Single negative integer |
| `"[123,[456,[789]]]"` | Standard nested example |
| `"[-1,[2,-3],4]"` | Negative values inside lists |
| `"[]"` | Empty list |
| `"[[]]"` | Nested empty list |
| `"[0,[10,-20],30]"` | Multi-digit and negative numbers |