Write sexpression(s: str) -> str. The input is supposed to describe a binary tree as a list of (parent,child) pairs; the parent comes first in each pair. Either print the tree as an S-expression or report what is wrong with the input.
Well-formed input is one or more pairs separated by exactly one space, with nothing before the first pair or after the last. Each pair is (, a node name, ,, a node name, ) with no spaces inside. A node name is one or more uppercase letters A-Z. Anything else (empty string, lowercase, digits, extra spaces, missing brackets, a trailing space, ...) is malformed.
If something is wrong, return the first code in this list that applies:
| code | problem |
|---|---|
"E1" |
the string is not well-formed |
"E2" |
the same (parent,child) pair appears more than once |
"E3" |
some parent has more than two distinct children |
"E4" |
more than one node has no parent, or some node has more than one parent |
"E5" |
the edges contain a cycle (including a node that is its own child, or input in which every node has a parent) |
Check them in that order: an input with both a duplicate pair and a cycle reports "E2".
If none applies, the pairs form one binary tree. Return S(root), where S(node) = "(" + name + S(first child) + S(second child) + ")", leaving out missing children. When a node has two children, the one whose name sorts first as a string goes first.
Inputs can have up to 100,000 pairs and trees can be a single long chain. Avoid anything quadratic, and don't rely on Python recursion: the default limit is about 1,000 frames.
sexpression("(A,B) (B,C) (A,D)") # "(A(B(C))(D))"
sexpression("(B,D) (D,E) (A,B) (C,F) (E,G) (A,C)") # "(A(B(D(E(G))))(C(F)))"
sexpression("(A,B) (A,C) (B,D) (D,C)") # "E4" (C has two parents)
sexpression("(A,B) (B,A)") # "E5"
sexpression("(A,B) (A,B)") # "E2"
sexpression("(A,B) (A,C) (A,D)") # "E3"
sexpression("(A,B) (A,C)") # "E1" (two spaces)