LeetCode //C - 385. Mini Parser

385. Mini Parser

Given a string s 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.
 

Example 1:

Input: s = “324”
Output: 324
Explanation: You should return a NestedInteger object which contains a single integer 324.

Example 2:

Input: s = “[123,[456,[789]]]”
Output: [123,[456,[789]]]
Explanation: Return a NestedInteger object containing a nested list with 2 elements:

1. An integer containing value 123.
2. A nested list containing two elements:
   i. An integer containing value 456.
   ii. A nested list with one element:
   a. An integer containing value 789

Constraints:

• $1<=s.length<=5\ast 10^4$
• s consists of digits, square brackets “[]”, negative sign ‘-’, and commas ‘,’.
• s is the serialization of valid NestedInteger.
• All the values in the input are in the range $[-10^6,10^6]$.

From: LeetCode
Link: 385. Mini Parser

Solution:

Ideas:

• Handling integers: If s doesn’t start with a [, it’s a single integer, so we parse it using atoi and return a NestedInteger containing that integer.
• Handling lists: We traverse through the string character by character.
  • When encountering [, we initialize a new NestedInteger and push the current one onto a stack if necessary.
  • When encountering ], we pop from the stack and add the current NestedInteger to the parent.
  • When encountering digits (or - for negative numbers), we parse the number and add it to the current list.
• Memory management: We use a stack to keep track of nested structures, and when we close a nested list (]), we pop the stack and add the nested structure to its parent.

Code:

/**
 * *********************************************************************
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * *********************************************************************
 *
 * // Initializes an empty nested list and return a reference to the nested integer.
 * struct NestedInteger *NestedIntegerInit();
 *
 * // Return true if this NestedInteger holds a single integer, rather than a nested list.
 * bool NestedIntegerIsInteger(struct NestedInteger *);
 *
 * // 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 NestedIntegerGetInteger(struct NestedInteger *);
 *
 * // Set this NestedInteger to hold a single integer.
 * void NestedIntegerSetInteger(struct NestedInteger *ni, int value);
 *
 * // Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
 * void NestedIntegerAdd(struct NestedInteger *ni, struct NestedInteger *elem);
 *
 * // 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
 * struct NestedInteger **NestedIntegerGetList(struct NestedInteger *);
 *
 * // Return the nested list's size that this NestedInteger holds, if it holds a nested list
 * // The result is undefined if this NestedInteger holds a single integer
 * int NestedIntegerGetListSize(struct NestedInteger *);
 * };
 */

struct NestedInteger* deserialize(char* s) {
    // Handle a special case where the input is just a single integer
    if (s[0] != '[') {
        // Single integer case
        struct NestedInteger* ni = NestedIntegerInit();
        NestedIntegerSetInteger(ni, atoi(s));
        return ni;
    }

    // Stack to hold NestedInteger objects
    struct NestedInteger** stack = (struct NestedInteger**)malloc(50000 * sizeof(struct NestedInteger*));
    int top = -1;  // Stack top pointer
    int i = 0, n = 0, negative = 0;

    struct NestedInteger* curr = NULL;

    while (s[i]) {
        char ch = s[i];
        if (ch == '[') {
            // Start a new NestedInteger list
            struct NestedInteger* ni = NestedIntegerInit();
            if (curr != NULL) {
                stack[++top] = curr;
            }
            curr = ni;
        } else if (ch == ']') {
            // End of current NestedInteger list, pop from stack and add to parent if exists
            if (top != -1) {
                struct NestedInteger* parent = stack[top--];
                NestedIntegerAdd(parent, curr);
                curr = parent;
            }
        } else if (ch == ',') {
            // Skip commas
        } else {
            // Handle number parsing
            int num = 0;
            negative = 0;

            if (s[i] == '-') {
                negative = 1;
                i++;
            }

            while (isdigit(s[i])) {
                num = num * 10 + (s[i] - '0');
                i++;
            }
            if (negative) num = -num;
            
            // Set this as a NestedInteger containing a single integer
            struct NestedInteger* ni = NestedIntegerInit();
            NestedIntegerSetInteger(ni, num);
            
            // Add it to the current list
            NestedIntegerAdd(curr, ni);

            // Move the index back by one as the outer loop will increment it
            i--;
        }
        i++;
    }

    free(stack);
    return curr;
}