Compilers: Draw the tree

Build an AST from an expression and show its shape.

What to build

A program that parses an infix expression and prints its abstract syntax tree, one node per line.

Requirements

  • Operators + - * / with the usual precedence, grouped from the left; brackets group; leaves are numbers and names.
  • Print each operator node as its symbol and each leaf as itself, indented by two spaces per level, with the root at the left and the left child before the right.

Input

One line: an expression.

Output

One line per node.

Constraints

At most 80 characters; the expression is valid.

Example

Input:

1 + 2 * 3

Output:

+
  1
  *
    2
    3

Why it works

The indentation shows exactly how the parser grouped the expression; brackets in the input are gone, but their effect remains in the shape.

Examples

Example 1 · Input
1 + 2 * 3
Expected output
+
  1
  *
    2
    3
Example 2 · Input
(a + b) * c
Expected output
*
  +
    a
    b
  c

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Parse with expr (+ −) calling term (* /) calling atom, building nested nodes such as (op, left, right).

Hint 2

Print a node, then its children with two more spaces of indentation.

Solution

Show one correct solution (try it yourself first)
import re

tokens = re.findall(r"\d+|\w+|\S", input())
pos = 0


def peek():
    return tokens[pos] if pos < len(tokens) else None


def take():
    global pos
    pos += 1
    return tokens[pos - 1]


def expr():
    node = term()
    while peek() in ("+", "-"):
        node = (take(), node, term())
    return node


def term():
    node = atom()
    while peek() in ("*", "/"):
        node = (take(), node, atom())
    return node


def atom():
    token = take()
    if token == "(":
        node = expr()
        take()
        return node
    return token


def draw(node, depth=0):
    if isinstance(node, str):
        print("  " * depth + node)
    else:
        print("  " * depth + node[0])
        draw(node[1], depth + 1)
        draw(node[2], depth + 1)


draw(expr())

Lesson: Abstract syntax trees →