Compilers: Show the grouping with brackets

Make precedence and associativity visible.

What to build

A program that adds brackets around every operation, showing how the parser groups the expression.

Requirements

    • and / bind tighter than + and −; operators of the same level group from the left.
  • Print the expression with no spaces, a pair of brackets around each operation, and numbers unchanged.

Input

One line: an expression with whole numbers, + - * /, 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

The brackets show exactly the tree the parser builds: lower precedence wraps higher precedence, and loops group from the left.

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

Parse with expr (for + −) calling term (for * /) calling factor, and return strings.

Hint 2

Wrap every binary operation as "(" + left + op + right + ")".

Solution

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

tokens = re.findall(r"\d+|[-+*/()]", 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():
    left = term()
    while peek() in ("+", "-"):
        op = take()
        left = f"({left}{op}{term()})"
    return left


def term():
    left = factor()
    while peek() in ("*", "/"):
        op = take()
        left = f"({left}{op}{factor()})"
    return left


def factor():
    if peek() == "(":
        take()
        inside = expr()
        take()
        return inside
    return take()


print(expr())

Lesson: Recursive-descent parsing →