Compilers: Measure a tree

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: L and depth: 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)

Lesson: Abstract syntax trees →