Postfix expression evaluation in Python
Evaluates an expression in postfix notation by scanning left to right and using a stack to hold operands.
- File
postfix_evaluation.py, 53 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/postfix-evaluation/. The authors are listed in prov/XVTXFV.jsonl.
from collections.abc import Callable, Mapping, Sequence
from fractions import Fraction
Op = tuple[int, Callable[..., Fraction]]
DEFAULT_OPS: Mapping[str, Op] = {
"+": (2, lambda a, b: a + b),
"-": (2, lambda a, b: a - b),
"*": (2, lambda a, b: a * b),
"/": (2, lambda a, b: a / b),
"neg": (1, lambda a: -a),
}
class MalformedExpression(ValueError):
"""The token string is not a postfix expression."""
def postfix_eval(tokens: Sequence[str], ops: Mapping[str, Op] = DEFAULT_OPS) -> Fraction:
"""Return the exact value of the postfix expression given as a list of tokens.
A token that is a key of ops is an operator with the given arity and
function; every other token must be an integer literal such as "12" or
"-3". Raises MalformedExpression if the tokens are not one postfix
expression, and ZeroDivisionError on a division by zero.
Cost: Theta(m) stack operations for m tokens, Theta(m) extra space worst case.
"""
s: list[Fraction] = [] # @line L1
for tok in tokens: # @line L2
if tok not in ops:
try:
value = Fraction(int(tok))
except ValueError:
raise MalformedExpression(f"unknown token {tok!r}") from None
s.append(value) # @line L3
else:
k, f = ops[tok] # @line L4
if len(s) < k: # @line L5
raise MalformedExpression(f"too few operands for {tok!r}")
y = s[len(s) - k :] # @line L6: y[0] is the first operand, y[-1] was the top
del s[len(s) - k :]
s.append(f(*y)) # @line L7
if len(s) != 1: # @line L8
raise MalformedExpression(f"{len(s)} values left, not one")
return s.pop() # @line L9
def evaluate(text: str, ops: Mapping[str, Op] = DEFAULT_OPS) -> Fraction:
"""Split text on white space and evaluate it with postfix_eval."""
return postfix_eval(text.split(), ops)
test_postfix_evaluation.py 94 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/postfix-evaluation/. The authors are listed in prov/XVTXFV.jsonl.
import random
from fractions import Fraction
from functools import lru_cache
import pytest
from postfix_evaluation import DEFAULT_OPS, MalformedExpression, evaluate, postfix_eval
def test_example() -> None:
assert evaluate("5 1 2 + 4 * + 3 -") == 14
assert evaluate("3 4 + 2 *") == 14
assert evaluate("3 4 2 * +") == 11
def test_edges() -> None:
assert evaluate("7") == 7
assert evaluate("-3") == -3
assert evaluate("-3 neg") == 3
assert evaluate("1 2 3 4 + + +") == 10
assert evaluate("1 2 + 3 + 4 +") == 10
big = 2**63 - 1
assert evaluate(f"{big} {big} *") == big * big
assert evaluate("1 3 /") == Fraction(1, 3)
def test_operand_order() -> None:
assert evaluate("7 2 -") == 5
assert evaluate("8 2 /") == 4
assert evaluate("2 8 /") == Fraction(1, 4)
def test_malformed() -> None:
for text in ["", "3 +", "3 4", "3 4 + +", "+", "3 x +", "1 2 3 +"]:
with pytest.raises(MalformedExpression):
evaluate(text)
with pytest.raises(ZeroDivisionError):
evaluate("1 0 /")
OPS = ["+", "-", "*", "neg"]
def oracle(tokens: tuple[str, ...]) -> Fraction | None:
"""Parse by trying every split (independent of the stack and of the counting test)."""
@lru_cache(maxsize=None)
def parse(i: int, j: int) -> Fraction | None:
if j - i == 1 and tokens[i] not in DEFAULT_OPS:
return Fraction(int(tokens[i]))
if j - i < 2 or tokens[j - 1] not in DEFAULT_OPS:
return None
k, f = DEFAULT_OPS[tokens[j - 1]]
if k == 1:
a = parse(i, j - 1)
return None if a is None else f(a)
for c in range(i + 1, j - 1):
a, b = parse(i, c), parse(c, j - 1)
if a is not None and b is not None:
return f(a, b)
return None
return parse(0, len(tokens)) if tokens else None
def random_tree_postfix(rng: random.Random, depth: int) -> list[str]:
if depth == 0 or rng.random() < 0.3:
return [str(rng.randint(-9, 9))]
op = rng.choice(OPS)
if op == "neg":
return random_tree_postfix(rng, depth - 1) + [op]
return random_tree_postfix(rng, depth - 1) + random_tree_postfix(rng, depth - 1) + [op]
def test_random_well_formed_against_oracle() -> None:
rng = random.Random(1954)
for _ in range(500):
toks = random_tree_postfix(rng, rng.randint(0, 5))
assert postfix_eval(toks) == oracle(tuple(toks))
def test_random_strings_against_oracle() -> None:
rng = random.Random(1962)
for _ in range(1000):
toks = tuple(rng.choice(["1", "2", "-3", "+", "-", "*", "neg"]) for _ in range(rng.randint(0, 9)))
want = oracle(toks)
if want is None:
with pytest.raises(MalformedExpression):
postfix_eval(toks)
else:
assert postfix_eval(toks) == want
What the next level needs
- the tests did not run in this build