Compilers: Evaluate while reducing

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 error if 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

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

Lesson: Bottom-up parsing: shift and reduce →