Mini Parser - Practice Coding Problems

Mini Parser - Problem

Given a string s that represents the serialization of a nested list, implement a parser to deserialize it and return the deserialized NestedInteger.

Each element is either an integer or a list whose elements may also be integers or other lists.

The format follows these rules:

An integer is just a number (positive, negative, or zero)
A list starts with [ and ends with ]
Elements in a list are separated by commas
Lists can be nested to any depth

Examples:

"324" → single integer 324
"[123,456]" → list containing two integers
"[123,[456,789]]" → list containing an integer and a nested list

Input & Output

Example 1 — Single Integer

$ Input: s = "324"

› Output: 324

💡 Note: The input represents a single integer, so we parse and return the number 324.

Example 2 — Simple List

$ Input: s = "[123,456]"

› Output: [123,456]

💡 Note: The input represents a list with two integers. We parse the brackets and comma-separated values to return [123,456].

Example 3 — Nested List

$ Input: s = "[123,[456,789]]"

› Output: [123,[456,789]]

💡 Note: The input has a nested structure: a list containing an integer (123) and another list ([456,789]). We parse recursively to maintain the nesting.

Constraints

1 ≤ s.length ≤ 5 × 10⁴
s consists of digits, square brackets "[]", minus sign "-", and commas ","
s is the valid serialization of a NestedInteger
All integers in s are in the range [-10⁶, 10⁶]

Visualization

Tap to expand

Understanding the Visualization

Input

String representation of nested structure

Parse

Process characters to identify integers and lists

Output

Structured data with proper nesting

Key Takeaway

🎯 Key Insight: Use a stack to maintain context when parsing nested brackets, similar to matching parentheses but with data construction

Asked in

f Facebook 35 G Google 28 a Amazon 22 M Microsoft 18

The key insight is to use either recursion or a stack to handle the nested structure systematically. The stack approach is most intuitive: push new lists when encountering '[', parse numbers between delimiters, and pop completed lists when encountering ']'. Time: O(n), Space: O(d) where d is the maximum nesting depth.

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Descent Parser	O(n)	O(d)	Parse recursively by identifying integers vs lists and handling each case
Stack-Based Parser	O(n)	O(d)	Use a stack to track current parsing context and build nested structure

Recursive Descent Parser — Algorithm Steps

Check if string starts with '[' (list) or digit/minus (integer)
For integers: parse the number directly
For lists: recursively parse each element between brackets

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Parsing

Begin at first character, identify list or integer

Recursive Calls

For each '[', make recursive call to parse contents

Build Result

Combine parsed elements into final structure

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

typedef struct NestedInteger {
    int isInteger;
    int intVal;
    struct NestedInteger** list;
    int listSize;
} NestedInteger;

int index_pos = 0;

NestedInteger* createInteger(int val) {
    NestedInteger* ni = malloc(sizeof(NestedInteger));
    ni->isInteger = 1;
    ni->intVal = val;
    ni->list = NULL;
    ni->listSize = 0;
    return ni;
}

NestedInteger* createList() {
    NestedInteger* ni = malloc(sizeof(NestedInteger));
    ni->isInteger = 0;
    ni->intVal = 0;
    ni->list = NULL;
    ni->listSize = 0;
    return ni;
}

void addToList(NestedInteger* list, NestedInteger* element) {
    list->list = realloc(list->list, (list->listSize + 1) * sizeof(NestedInteger*));
    list->list[list->listSize] = element;
    list->listSize++;
}

NestedInteger* parse(const char* s) {
    if (s[index_pos] == '[') {
        // Parse list
        index_pos++; // skip '['
        NestedInteger* nestedList = createList();
        // Handle empty list
        if (s[index_pos] == ']') {
            index_pos++;
            return nestedList;
        }
        
        while (1) {
            addToList(nestedList, parse(s));
            if (s[index_pos] == ']') {
                index_pos++;
                break;
            } else if (s[index_pos] == ',') {
                index_pos++; // skip comma
            }
        }
        return nestedList;
    } else {
        // Parse integer
        int start = index_pos;
        if (s[index_pos] == '-') {
            index_pos++;
        }
        while (index_pos < strlen(s) && isdigit(s[index_pos])) {
            index_pos++;
        }
        char numStr[20];
        strncpy(numStr, s + start, index_pos - start);
        numStr[index_pos - start] = '\0';
        return createInteger(atoi(numStr));
    }
}

void printNested(NestedInteger* ni) {
    if (ni->isInteger) {
        printf("%d", ni->intVal);
    } else {
        printf("[");
        for (int i = 0; i < ni->listSize; i++) {
            if (i > 0) printf(",");
            printNested(ni->list[i]);
        }
        printf("]");
    }
}

NestedInteger* solution(char* s) {
    index_pos = 0;
    return parse(s);
}

int main() {
    char s[10000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    NestedInteger* result = solution(s);
    printNested(result);
    printf("\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each character is processed exactly once during parsing

✓ Linear Growth

Space Complexity

O(d)

Recursion depth d equals maximum nesting level of lists

✓ Linear Space

32.2K Views

Medium Frequency

~25 min Avg. Time

896 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Descent Parser — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler