Compilers: Back to source with the fewest brackets

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

Example 1 · Input
((1+2))*3
Expected output
(1 + 2) * 3
Example 2 · Input
1+(2*3)
Expected output
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()))

Lesson: Abstract syntax trees →