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())