Validate and parse a bracketed list string

You are given a string s made of lowercase letters, commas, and the parentheses ( and ). A run of letters is a word. Commas separate items. A pair of parentheses wraps a group of items, and groups can nest.

Part 1

Implement is_well_formed(s: str) -> bool. Return True when every ) closes an earlier unmatched (, and every ( is closed. Letters and commas do not affect the result. The empty string is well-formed.

Part 2

Implement parse(s: str) -> list. Return the items of s as a nested list: each word becomes a string, and each group becomes a list of its own items, in order. Drop empty items (for example, the gap in a,,b). A word and a group next to each other, as in a(b), are separate items. Raise ValueError if the brackets are not well-formed.

Examples

is_well_formed("x,(y,(z)),w")  -> True
is_well_formed(")(")           -> False
is_well_formed("((a)")         -> False

parse("x,(y,(z)),w")  -> ["x", ["y", ["z"]], "w"]
parse("(a,b,c)")      -> [["a", "b", "c"]]
parse("()")           -> [[]]

Constraints

• 0 <= len(s) <= 10^5
• Nesting can be as deep as the length of s, so avoid recursion that could overflow the call stack.
• Aim for O(n) time.