Mini Parser

medium string stack dfs

Problem

Given a string s representing a NestedInteger (either a single integer or a possibly-nested list of NestedIntegers separated by commas), parse it and return the deserialized structure.

Inputs = "[123,[456,[789]]]"

Output[123,[456,[789]]]

Outer list holds 123 and an inner list that contains 456 and a deeper list [789].

def deserialize(s):
    if s[0] != '[':
        return int(s)
    stack, num, sign = [], '', 1
    cur = None
    for c in s:
        if c == '[':
            new = []
            if cur is not None: cur.append(new)
            stack.append(new); cur = new
        elif c == ']':
            if num: cur.append(sign * int(num)); num = ''
            sign = 1
            done = stack.pop()
            cur = stack[-1] if stack else done
        elif c == ',':
            if num: cur.append(sign * int(num)); num = ''
            sign = 1
        elif c == '-': sign = -1
        else: num += c
    return cur

function deserialize(s) {
  if (s[0] !== '[') return parseInt(s, 10);
  const stack = []; let num = '', sign = 1, cur = null;
  for (const c of s) {
    if (c === '[') {
      const arr = [];
      if (cur) cur.push(arr);
      stack.push(arr); cur = arr;
    } else if (c === ']') {
      if (num) { cur.push(sign * +num); num = ''; }
      sign = 1;
      const done = stack.pop();
      cur = stack.length ? stack[stack.length - 1] : done;
    } else if (c === ',') {
      if (num) { cur.push(sign * +num); num = ''; }
      sign = 1;
    } else if (c === '-') sign = -1;
    else num += c;
  }
  return cur;
}

class Solution {
    public NestedInteger deserialize(String s) {
        if (s.charAt(0) != '[') return new NestedInteger(Integer.parseInt(s));
        Deque<NestedInteger> stack = new ArrayDeque<>();
        NestedInteger cur = null; int num = 0, sign = 1; boolean hasNum = false;
        for (char c : s.toCharArray()) {
            if (c == '[') { NestedInteger n = new NestedInteger(); if (cur != null) cur.add(n); stack.push(n); cur = n; }
            else if (c == ']') { if (hasNum) { cur.add(new NestedInteger(sign * num)); num = 0; sign = 1; hasNum = false; } NestedInteger done = stack.pop(); cur = stack.peek() == null ? done : stack.peek(); }
            else if (c == ',') { if (hasNum) { cur.add(new NestedInteger(sign * num)); num = 0; sign = 1; hasNum = false; } }
            else if (c == '-') sign = -1;
            else { num = num * 10 + (c - '0'); hasNum = true; }
        }
        return cur;
    }
}

NestedInteger deserialize(string s) {
    if (s[0] != '[') return NestedInteger(stoi(s));
    stack<NestedInteger> st; NestedInteger cur; int num = 0, sign = 1; bool hasNum = false;
    for (char c : s) {
        if (c == '[') { st.push(NestedInteger()); }
        else if (c == ']') {
            if (hasNum) { st.top().add(NestedInteger(sign * num)); num = 0; sign = 1; hasNum = false; }
            NestedInteger done = st.top(); st.pop();
            if (st.empty()) return done; else st.top().add(done);
        }
        else if (c == ',') { if (hasNum) { st.top().add(NestedInteger(sign * num)); num = 0; sign = 1; hasNum = false; } }
        else if (c == '-') sign = -1;
        else { num = num * 10 + (c - '0'); hasNum = true; }
    }
    return cur;
}

Explanation

The string describes nested lists, and a stack is the natural tool for tracking which list we are currently filling. Each time we open a bracket we start a new list; each time we close one we finish it and fall back to its parent.

First, the easy case: if the string does not start with [, it is a plain integer and we just return int(s). Otherwise we scan character by character, building numbers digit by digit in num and remembering a negative sign when we see -.

On [ we create a new empty list, attach it to the current list cur if one exists, push it on the stack, and make it the new cur. On , or ] we flush any pending number into cur. On ] we also pop the finished list and set cur back to the parent on top of the stack.

Example: "[123,[456,[789]]]". The first [ opens the outer list; 123 is flushed at the comma; the next [ opens an inner list attached to the outer one; 456 is added; a deeper [789] nests inside; and each ] closes back up to the parent, yielding [123,[456,[789]]].

It works because the stack always mirrors the current nesting path, so a new value or sublist is always added to exactly the right level, and popping on ] returns control to the enclosing list.

Time: O(n) Space: O(d) (max nesting depth)