Attach semantic actions to reductions, the way parser generators compute results.
What to build
A program that evaluates an integer expression with a shift-reduce parser, computing at every reduction.
Requirements
- Tokens: whole numbers,
+ - * /and brackets. Use the precedence rules of the previous exercise, with − beside + and / beside *. - Print the value, or
syntax errorif the parser cannot accept.
Input
One line: an expression (tokens may be written without spaces).
Output
One line.
Constraints
At most 60 characters; no division by zero; no unary minus.
Example
Input:
2 + 3 * 4
Output:
14
Why it works
Each reduction is one complete operation, so computing the value at the moment of reducing evaluates the expression in exactly the right order.
Examples
2 + 3 * 4
14
(2 + 3) * 4
20
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Keep values on the stack: a number token becomes ("E", value) when reduced, and reducing E op E computes the result.
Hint 2
+ and − share one precedence level, * and / a higher one; all four are left-associative, and / is //.
Solution
Show one correct solution (try it yourself first)
import re
PREC = {"+": 1, "-": 1, "*": 2, "/": 2}
tokens = re.findall(r"\d+|[-+*/()]", input()) + ["$"]
stack, i = [], 0
result = None
while result is None:
a = tokens[i]
if stack and isinstance(stack[-1], str) and stack[-1].isdigit():
stack[-1] = ("E", int(stack[-1]))
elif len(stack) >= 3 and stack[-3] == "(" and isinstance(stack[-2], tuple) and stack[-1] == ")":
stack[-3:] = [stack[-2]]
elif (
len(stack) >= 3
and isinstance(stack[-1], tuple)
and stack[-2] in PREC
and isinstance(stack[-3], tuple)
and (a in ("$", ")") or (a in PREC and PREC[a] <= PREC[stack[-2]]))
):
x, op, y = stack[-3][1], stack[-2], stack[-1][1]
stack[-3:] = [("E", {"+": x + y, "-": x - y, "*": x * y, "/": x // y}[op])]
elif a == "$":
result = str(stack[0][1]) if len(stack) == 1 and isinstance(stack[0], tuple) else "syntax error"
else:
stack.append(a)
i += 1
print(result)