Validate and parse a bracketed list string

The string has three kinds of characters: lowercase letters (which form words), commas (which separate items), and parentheses (which open and close groups). The problem usually comes in two parts. Part 1 asks whether the brackets are well-formed. Part 2 asks you to turn the string into nested lists. Both parts are one left-to-right scan with a stack.

Part 1: validate. Only one bracket type exists, so the stack holds nothing useful except its height. A single counter depth is enough:

• On (, add one.
• On ), subtract one. If depth goes below zero, a ) has no matching (, so the string is not well-formed. Stop at once.
• Letters and commas do not change depth.
• At the end, the string is well-formed only if depth == 0. A positive value means some ( never closed.

The invariant is: after reading any prefix, depth is the number of open groups still waiting for a ). That number can never be negative. The empty string is well-formed.

A common brute force is to delete () pairs again and again until nothing changes. It works, but it is O(n^2). Say it once and then move to the counter.

Part 2: parse into nested lists. Now the stack holds real lists. stack[-1] is the list that new items go into, and stack[0] is the top-level result.

• Letter: add it to the current word buffer.
• Comma: flush the buffer (append the word to stack[-1] if it is not empty).
• (: flush the buffer, make a new empty list, append it to stack[-1], and push it. Appending at open time keeps the group in its correct position among its siblings.
• ): flush the buffer, then pop. If only the top-level list is left on the stack, the ) is unmatched. Raise an error.
• At the end, flush the buffer. If more than one list is on the stack, a group never closed. Raise an error.

Flushing on every delimiter, not only on commas, handles inputs such as a(b) and (a)b. The word and the group are separate items even without a comma. Empty items, such as those in a,,b or (,), are dropped. Ask the interviewer about this rule early, because it is the main open choice in the spec.

Part 2 validates while it parses, so the parser does not need a separate pass from Part 1.

from typing import List, Union

Item = Union[str, "Nested"]
Nested = List[Item]


def is_well_formed(s: str) -> bool:
    """Part 1: every ')' matches an earlier '(' and every '(' is closed."""
    depth = 0
    for ch in s:
        if ch == "(":
            depth += 1
        elif ch == ")":
            depth -= 1
            if depth < 0:
                return False
    return depth == 0


def parse(s: str) -> Nested:
    """Part 2: words become strings, each (...) group becomes a nested list.

    Commas separate items. Empty items are dropped.
    Raises ValueError if the brackets are not well-formed.
    """
    root: Nested = []
    stack: List[Nested] = [root]
    word: List[str] = []

    def flush() -> None:
        if word:
            stack[-1].append("".join(word))
            word.clear()

    for i, ch in enumerate(s):
        if ch.isalpha():
            word.append(ch)
        elif ch == ",":
            flush()
        elif ch == "(":
            flush()
            group: Nested = []
            stack[-1].append(group)
            stack.append(group)
        elif ch == ")":
            flush()
            if len(stack) == 1:
                raise ValueError(f"unmatched ')' at index {i}")
            stack.pop()
        elif ch.isspace():
            flush()
        else:
            raise ValueError(f"unexpected character {ch!r} at index {i}")

    flush()
    if len(stack) != 1:
        raise ValueError(f"{len(stack) - 1} unclosed '('")
    return root


if __name__ == "__main__":
    assert is_well_formed("")
    assert is_well_formed("x,(y,(z)),w")
    assert not is_well_formed(")(")
    assert not is_well_formed("((a)")
    assert not is_well_formed("a)")

    assert parse("") == []
    assert parse("cat") == ["cat"]
    assert parse("x,(y,(z)),w") == ["x", ["y", ["z"]], "w"]
    assert parse("()") == [[]]
    assert parse("(a,b,c)") == [["a", "b", "c"]]
    assert parse("a,,b") == ["a", "b"]
    assert parse("a(b)c") == ["a", ["b"], "c"]
    assert parse("((()))") == [[[[]]]]
    for bad in [")(", "((a)", "a)", "(()"]:
        try:
            parse(bad)
            raise AssertionError(bad)
        except ValueError:
            pass
    print("ok")

• is_well_formed: O(n) time, O(1) extra space.
• parse: O(n) time. Each character is read once, and each word is joined once. Space is O(n) for the output plus O(d) for the stack, where d is the maximum nesting depth.

• is_well_formed("") returns True. Empty input has no unmatched brackets.
• is_well_formed("x,(y,(z)),w") returns True.
• is_well_formed(")(") returns False. The counts balance, but ) comes first.
• is_well_formed("((a)") returns False. One ( is never closed.
• parse("cat") returns ["cat"].
• parse("x,(y,(z)),w") returns ["x", ["y", ["z"]], "w"].
• parse("()") returns [[]]. An empty group is still an item.
• parse("(a,b,c)") returns [["a", "b", "c"]]. Note the two brackets: the top level is a list that holds one group.
• parse("a,,b") returns ["a", "b"]. The empty item is dropped.
• parse("a(b)c") returns ["a", ["b"], "c"]. Brackets separate items without a comma.
• parse("((()))") returns [[[[]]]].
• parse("(()") raises ValueError (one unclosed ().
• parse("a)") raises ValueError (unmatched ) at index 1).

1. Depth-tagged tokens instead of brackets. The input becomes a list of (depth, word) pairs, such as [(0, "x"), (1, "y"), (2, "z"), (0, "w")]. Keep the same stack of lists. Before you append a word at depth d, pop while len(stack) - 1 > d, then push new empty lists while len(stack) - 1 < d. A jump of more than one level either creates the empty intermediate groups or is an error. Agree on which with the interviewer. This is still O(n).
2. Serialize back. Write the inverse: a recursive function that joins items with commas and wraps each sub-list in parentheses. serialize(parse(s)) equals s after normalization (no empty items). This makes a good property test.
3. Report the error position. Return the index of the first bad ) or of the oldest unclosed (. For the second case, keep a stack of opening indices instead of a plain counter. The bottom of that stack at the end is the answer.
4. Several bracket types. Add [] and {}. The counter no longer works. Push the opening character and check that each closer matches the top of the stack. This is exactly LeetCode 20.
5. Very deep nesting or streaming input. The parser is already iterative, so deep input cannot overflow the call stack, unlike a recursive-descent version. For a stream, feed one chunk at a time and keep stack and word between chunks. Emit each top-level item when the stack falls back to depth 0.

Mid-level (L4)

• Solves Part 1 with a counter or stack, and checks both the "below zero" case and the "nonzero at the end" case.
• Gets Part 2 working with a stack of lists, perhaps after one or two bugs with flushing the last word.
• Tests the empty string and an empty group.

Senior (L5)

• Asks how to treat empty items, words next to brackets, and other characters before coding.
• Notices that the parser validates as a side effect, so it does not need a second pass.
• Writes the code iteratively, explains the stack invariant, and handles the depth-token follow-up without starting again.

Staff (L6+)

• Gives clear error messages with positions, and explains the trade-off between strict and lenient parsing (reject a,,b or drop the empty item).
• Talks about round-tripping with a serializer and property tests, and about streaming input and very deep nesting.
• Connects the problem to real parsers (a small grammar, recursive descent compared with an explicit stack) and to how a rich-text editor would use the nested structure.