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 ^ 2is(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())