Read a tree written in prefix form and measure it.
What to build
A program that counts the nodes and leaves of an expression tree and finds its depth.
Requirements
- A tree is a leaf (a number or a name) or
(op child child …)with one or more children. The operator and every leaf count as one node each. - Print
nodes: N,leaves: Landdepth: D, where a single leaf has depth 1.
Input
One line: a tree in prefix form.
Output
Three lines.
Constraints
At most 100 characters.
Example
Input:
(+ 1 (* 2 3))
Output:
nodes: 5
leaves: 3
depth: 3
Why it works
A tree is defined in terms of smaller trees, so every measure is a short recursive function.
Examples
Example 1 · Input
(+ 1 (* 2 3))
Expected output
nodes: 5 leaves: 3 depth: 3
Example 2 · Input
x
Expected output
nodes: 1 leaves: 1 depth: 1
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Read the prefix form recursively: a bracket starts a node whose first item is the operator; anything else is a leaf.
Hint 2
Count nodes and leaves and find the depth with one recursive function each, or one that returns all three.
Solution
Show one correct solution (try it yourself first)
import re
tokens = re.findall(r"\(|\)|[^\s()]+", input())
def read():
token = tokens.pop(0)
if token != "(":
return token
items = []
while tokens[0] != ")":
items.append(read())
tokens.pop(0)
return items
def measure(node):
if isinstance(node, str):
return 1, 1, 1
nodes, leaves, depth = 1, 0, 0
for child in node[1:]:
n, l, d = measure(child)
nodes, leaves, depth = nodes + n, leaves + l, max(depth, d)
return nodes, leaves, depth + 1
nodes, leaves, depth = measure(read())
print("nodes:", nodes)
print("leaves:", leaves)
print("depth:", depth)