# Mini Parser
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/mini-parser)
Canonical: https://scaleengineer.com/dsa/problems/mini-parser
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** String, Stack
**Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb)
---
## Problem
\[Fetch error\]

# Approaches
## Recursive Parsing (Depth-First)
This approach leverages recursion, which is a natural fit for parsing nested or tree-like data structures. The function calls itself to handle nested lists, effectively performing a depth-first traversal of the nested structure represented by the string.
**Time:** O(N), where N is the length of the input string. Each character of the string is examined a constant number of times. · **Space:** O(D), where D is the maximum nesting depth of the list. In the worst-case scenario (e.g., `"[[[[...]]]]"`), the depth D can be proportional to the length of the string N, making the space complexity O(N). This space is used by the recursion call stack.
**Pros:** The code is often more concise and easier to understand because it directly mirrors the nested definition of the data structure.; It's a very natural way to think about problems involving recursion and nested hierarchies.
**Cons:** For very deeply nested input strings, this approach can lead to a `StackOverflowError` due to deep recursion.; The overhead of function calls might make it slightly less performant than an iterative solution.
### Explanation
We can design a recursive function that is responsible for parsing one `NestedInteger` element from the string, starting at a given index. Since we need to keep track of our progress through the string across recursive calls, we can pass an index by reference (e.g., using a single-element array `int[]`) or use a class member for the index.

The base case for the recursion is a number. If the substring to be parsed does not start with `'['`, we parse it as an integer.

The recursive step handles lists. If the substring starts with `'['`, we create a new `NestedInteger` to act as a list. We then iterate, recursively calling the function to parse each element within the brackets until we encounter the closing `']'`. Commas are used as delimiters to separate elements.

```java
/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    private int index = 0;

    public NestedInteger deserialize(String s) {
        // If the string doesn't start with '[', it's a single integer.
        // This check is implicitly handled by the logic below.
        return parse(s);
    }

    private NestedInteger parse(String s) {
        if (s.charAt(index) == '[') {
            index++; // Skip '['
            NestedInteger ni = new NestedInteger();
            while (s.charAt(index) != ']') {
                ni.add(parse(s));
                if (s.charAt(index) == ',') {
                    index++; // Skip ','
                }
            }
            index++; // Skip ']'
            return ni;
        } else {
            // It's a number
            int start = index;
            while (index < s.length() && (Character.isDigit(s.charAt(index)) || s.charAt(index) == '-')) {
                index++;
            }
            int num = Integer.parseInt(s.substring(start, index));
            return new NestedInteger(num);
        }
    }
}
```
### Algorithm
- The core idea is to use a recursive helper function that parses a portion of the string and advances a global or passed-by-reference index.
- The main `deserialize` function checks if the string represents a single number (i.e., does not start with `[`). If so, it parses it and returns.
- Otherwise, it calls a recursive helper function to parse the list.
- The recursive helper function, say `parse(s, index)`:
  - If the character at the current index is `'['`, it knows it's parsing a list. It creates a new `NestedInteger` list.
  - It then enters a loop, continuing as long as the character at the index is not `']'`. Inside the loop, it recursively calls `parse` to get the next element (which could be a number or another list) and adds it to the current list.
  - It handles commas by simply advancing the index.
  - Once it hits `']'`, it advances the index past it and returns the created list.
  - If the character at the current index is a digit or a `'-'`, it knows it's parsing a number. It reads all consecutive digits to form the number string, parses it to an integer, creates a `NestedInteger` with this value, and returns it.

## Iterative Parsing with a Stack
An iterative approach using a stack can solve the problem without recursion, thus avoiding potential stack overflow issues. The stack is used to manage the hierarchy of nested lists. The top of the stack always holds the parent list to which new elements (numbers or sub-lists) should be added.
**Time:** O(N), where N is the length of the input string. The string is traversed once from left to right. · **Space:** O(D), where D is the maximum nesting depth. In the worst case, like `"[[[[...]]]]"`, the depth D can be O(N), where N is the string length. This space is used by the explicit stack.
**Pros:** It is robust against very deep nesting levels as it does not rely on the program's call stack, thus avoiding `StackOverflowError`.; It can be marginally more performant by avoiding the overhead associated with function calls.
**Cons:** The logic can be more complex to write and debug compared to the recursive approach.; Managing the state (stack, current pointer, number start index) requires careful implementation.
### Explanation
This method manually manages the nested structure using an explicit stack. It iterates through the string, building up the `NestedInteger` structure as it goes.

When a `'['` is encountered, it signifies a new level of nesting. We create a new `NestedInteger` list and push the previous list (the parent) onto the stack. This new list becomes the `current` one we're adding elements to.

When a number is found (a sequence of digits, possibly with a sign), we parse it and add it as a `NestedInteger` to the `current` list.

When a `']'` is encountered, it means we've finished constructing the `current` list. We add any pending number right before it. Then, we pop from the stack to retrieve its parent, add the `current` list to this parent, and make the parent the new `current` list. This effectively moves us up one level in the hierarchy.

```java
/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // ... (interface methods as defined in the problem)
 * }
 */
class Solution {
    public NestedInteger deserialize(String s) {
        if (s == null || s.isEmpty()) {
            return new NestedInteger();
        }
        if (s.charAt(0) != '[') {
            return new NestedInteger(Integer.parseInt(s));
        }

        Stack<NestedInteger> stack = new Stack<>();
        NestedInteger current = null;
        int l = 0; // left pointer for substring

        for (int r = 0; r < s.length(); r++) {
            char ch = s.charAt(r);
            if (ch == '[') {
                if (current != null) {
                    stack.push(current);
                }
                current = new NestedInteger();
                l = r + 1;
            } else if (ch == ']') {
                String numStr = s.substring(l, r);
                if (!numStr.isEmpty()) {
                    current.add(new NestedInteger(Integer.parseInt(numStr)));
                }
                if (!stack.isEmpty()) {
                    NestedInteger parent = stack.pop();
                    parent.add(current);
                    current = parent;
                }
                l = r + 1;
            } else if (ch == ',') {
                // A comma can only appear after a number or a closing bracket ']' 
                if (s.charAt(r - 1) != ']') {
                    String numStr = s.substring(l, r);
                    if (!numStr.isEmpty()) {
                        current.add(new NestedInteger(Integer.parseInt(numStr)));
                    }
                }
                l = r + 1;
            }
        }
        return current;
    }
}
```
### Algorithm
- First, handle the edge case where the string represents a single number (it doesn't start with `[`). Parse and return it directly.
- For list strings, use a `Stack` to keep track of the parent `NestedInteger` lists.
- Initialize a `current` `NestedInteger` pointer, which will hold the list or integer being constructed. 
- Iterate through the string character by character:
  - If you see `'['`: This is the start of a new list. If `current` is not null, push it to the stack (it's the parent). Then, create a new empty `NestedInteger` and assign it to `current`.
  - If you see `']'`: This is the end of a list. First, parse any pending number that comes just before the `]`. Then, if the stack is not empty, it means the `current` list is a sub-list. Pop the parent from the stack, add `current` to it, and update `current` to be the parent.
  - If you see `','`: This signals the end of an element. Parse any pending number before the comma and add it to the `current` list.
- A pointer `l` can be used to mark the start of a number segment to facilitate parsing.

# Solutions
### Java

```java
/** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * public interface NestedInteger { * // Constructor initializes an empty nested list. * public NestedInteger(); * * // Constructor initializes a single integer. * public NestedInteger(int value); * * // @return true if this NestedInteger holds a single integer, rather than a nested list. * public boolean isInteger(); * * // @return the single integer that this NestedInteger holds, if it holds a single integer * // Return null if this NestedInteger holds a nested list * public Integer getInteger(); * * // Set this NestedInteger to hold a single integer. * public void setInteger(int value); * * // Set this NestedInteger to hold a nested list and adds a nested integer to it. * public void add(NestedInteger ni); * * // @return the nested list that this NestedInteger holds, if it holds a nested list * // Return empty list if this NestedInteger holds a single integer * public List<NestedInteger> getList(); * } */ class Solution { public NestedInteger deserialize ( String s ) { if ( s . charAt ( 0 ) != '[' ) { return new NestedInteger ( Integer . parseInt ( s )); } Deque < NestedInteger > stk = new ArrayDeque <>(); int x = 0 ; boolean neg = false ; for ( int i = 0 ; i < s . length (); ++ i ) { char c = s . charAt ( i ); if ( c == '-' ) { neg = true ; } else if ( Character . isDigit ( c )) { x = x * 10 + c - '0' ; } else if ( c == '[' ) { stk . push ( new NestedInteger ()); } else if ( c == ',' || c == ']' ) { if ( Character . isDigit ( s . charAt ( i - 1 ))) { if ( neg ) { x = - x ; } stk . peek (). add ( new NestedInteger ( x )); } x = 0 ; neg = false ; if ( c == ']' && stk . size () > 1 ) { NestedInteger t = stk . pop (); stk . peek (). add ( t ); } } } return stk . peek (); } }
```

### CPP

```cpp
/** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * class NestedInteger { * public: * // Constructor initializes an empty nested list. * NestedInteger(); * * // Constructor initializes a single integer. * NestedInteger(int value); * * // Return true if this NestedInteger holds a single integer, rather than a nested list. * bool isInteger() const; * * // Return the single integer that this NestedInteger holds, if it holds a single integer * // The result is undefined if this NestedInteger holds a nested list * int getInteger() const; * * // Set this NestedInteger to hold a single integer. * void setInteger(int value); * * // Set this NestedInteger to hold a nested list and adds a nested integer to it. * void add(const NestedInteger &ni); * * // Return the nested list that this NestedInteger holds, if it holds a nested list * // The result is undefined if this NestedInteger holds a single integer * const vector<NestedInteger> &getList() const; * }; */ class Solution { public: NestedInteger deserialize ( string s ) { if ( s [ 0 ] != '[' ) { return NestedInteger ( stoi ( s )); } stack < NestedInteger > stk ; int x = 0 ; bool neg = false ; for ( int i = 0 ; i < s . size (); ++ i ) { if ( s [ i ] == '-' ) { neg = true ; } else if ( isdigit ( s [ i ])) { x = x * 10 + s [ i ] - '0' ; } else if ( s [ i ] == '[' ) { stk . push ( NestedInteger ()); } else if ( s [ i ] == ',' || s [ i ] == ']' ) { if ( isdigit ( s [ i - 1 ])) { if ( neg ) { x = - x ; } stk . top (). add ( NestedInteger ( x )); } x = 0 ; neg = false ; if ( s [ i ] == ']' && stk . size () > 1 ) { auto t = stk . top (); stk . pop (); stk . top (). add ( t ); } } } return stk . top (); } };
```

### Python

```python
# """ # This is the interface that allows for creating nested lists. # You should not implement it, or speculate about its implementation # """ # class NestedInteger: # def __init__(self, value=None): # """ # If value is not specified, initializes an empty list. # Otherwise initializes a single integer equal to value. # """ # # def isInteger(self): # """ # @return True if this NestedInteger holds a single integer, rather than a nested list. # :rtype bool # """ # # def add(self, elem): # """ # Set this NestedInteger to hold a nested list and adds a nested integer elem to it. # :rtype void # """ # # def setInteger(self, value): # """ # Set this NestedInteger to hold a single integer equal to value. # :rtype void # """ # # def getInteger(self): # """ # @return the single integer that this NestedInteger holds, if it holds a single integer # Return None if this NestedInteger holds a nested list # :rtype int # """ # # def getList(self): # """ # @return the nested list that this NestedInteger holds, if it holds a nested list # Return None if this NestedInteger holds a single integer # :rtype List[NestedInteger] # """ class Solution : # recursion def deserialize ( self , s : str ) -> NestedInteger : if not s : return NestedInteger () if s [ 0 ] != '[' : return NestedInteger ( int ( s )) if len ( s ) <= 2 : # '[]' return NestedInteger () ans = NestedInteger () depth , i = 0 , 1 # i starting at 1, to skip first '[' for j in range ( 1 , len ( s )): if depth == 0 and ( s [ j ] == ',' or j == len ( s ) - 1 ): ans . add ( self . deserialize ( s [ i : j ])) # j at ']', exclusive i = j + 1 elif s [ j ] == '[' : depth += 1 elif s [ j ] == ']' : depth -= 1 return ans ############ ''' If we encounter an opening bracket [ we push the current nested list onto the stack and create a new nested list for the current level. If we encounter a closing bracket ] we add the current number (if any) to the current nested list, and if there are elements on the stack, we pop the top nested list from the stack and add the current nested list to it. If we encounter a comma , we add the current number (if any) to the current nested list. Otherwise, we append the character to the num string, which represents the number we are currently parsing. ''' class Solution : # iteration def deserialize ( self , s : str ) -> NestedInteger : if not s : return None if s [ 0 ] != '[' : return NestedInteger ( int ( s )) stack = [] # keep track of nested levels curr = None # current nested list that we are constructing num = "" for char in s : if char == '[' : if curr : stack . append ( curr ) curr = NestedInteger () elif char == ']' : if num : curr . add ( NestedInteger ( int ( num ))) num = "" if stack : pop_curr = curr curr = stack . pop () curr . add ( pop_curr ) elif char == ',' : if num : curr . add ( NestedInteger ( int ( num ))) num = "" else : num += char return curr
```