Turn a tree back into source text, as code formatters do.
What to build
A program that parses an expression and prints it again with single spaces around operators and only the brackets that are needed to keep the same tree.
Requirements
- Operators
+ - * /:* /bind tighter than+ -, and all four group from the left. - Keep a bracket only where removing it would change the tree. Leaves are numbers and names.
Input
One line: an expression (spaces optional, extra brackets allowed).
Output
One line.
Constraints
At most 80 characters; the expression is valid.
Example
Input:
((1+2))*3
Output:
(1 + 2) * 3
Why it works
Because the tree records the grouping, the brackets can be recomputed from the operators' precedence and position instead of being copied from the input.
Examples
((1+2))*3
(1 + 2) * 3
1+(2*3)
1 + 2 * 3
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
A left child needs brackets only if its operator binds more loosely than its parent's; a right child also needs them when the precedence is equal.
Hint 2
Parse into a tree first, then write a recursive unparse function that decides about brackets for each child.
Solution
Show one correct solution (try it yourself first)
import re
PREC = {"+": 1, "-": 1, "*": 2, "/": 2}
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 unparse(node):
if isinstance(node, str):
return node
op, left, right = node
l, r = unparse(left), unparse(right)
if not isinstance(left, str) and PREC[left[0]] < PREC[op]:
l = f"({l})"
if not isinstance(right, str) and PREC[right[0]] <= PREC[op]:
r = f"({r})"
return f"{l} {op} {r}"
print(unparse(expr()))