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())