Compilers: Parse to a tree in prefix form

Build the full expression tree, with unary minus and a right-associative power.

What to build

A program that parses an expression and prints its tree in Lisp-like prefix form.

Requirements

  • Precedence from lowest: + -, then * /, then prefix -, then ^. + - * / group from the left and ^ from the right; -x ^ 2 is (neg (^ x 2)).
  • Print each operation as (op child child) and a negation as (neg child); numbers and names as they are.

Input

One line: an expression with numbers, names, + - * / ^, brackets and spaces.

Output

One line.

Constraints

At most 60 characters; the expression is valid.

Example

Input:

1 + 2 * 3

Output:

(+ 1 (* 2 3))

Why it works

Prefix form shows the tree directly: each bracket is one node, its operator first and its children after.

Examples

Example 1 · Input
1 + 2 * 3
Expected output
(+ 1 (* 2 3))
Example 2 · Input
2 ^ 3 ^ 2
Expected output
(^ 2 (^ 3 2))

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

Hints

Hint 1

Use five levels: expr (+ −), term (* /), unary (prefix −), power (^, right-associative), atom.

Hint 2

Print a node as "(" op children ")", with neg for the prefix minus.

Solution

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

tokens = re.findall(r"\d+|[A-Za-z_]\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 = f"({take()} {node} {term()})"
    return node


def term():
    node = unary()
    while peek() in ("*", "/"):
        node = f"({take()} {node} {unary()})"
    return node


def unary():
    if peek() == "-":
        take()
        return f"(neg {unary()})"
    return power()


def power():
    base = atom()
    if peek() == "^":
        take()
        return f"(^ {base} {unary()})"
    return base


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


print(expr())

Lesson: Recursive-descent parsing →