Dijkstra's two-stack expression evaluation in Python

Evaluates a fully parenthesized arithmetic expression using one stack for operands and another for operators.

File: dijkstra_two_stack_evaluation.py, 39 lines
Level: I0 not checked yet
Toolchain: Python 3.14, pytest 9
Test framework: pytest
Run the tests: python3 -m pytest

dijkstra_two_stack_evaluation.pyRaw GitHub

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/dijkstra-two-stack-evaluation/. The authors are listed in prov/9KN9AK.jsonl.

from fractions import Fraction
from typing import Callable

OPS: dict[str, Callable[[Fraction, Fraction], Fraction]] = {
    "+": lambda a, b: a + b,
    "-": lambda a, b: a - b,
    "*": lambda a, b: a * b,
    "/": lambda a, b: a / b,
}


def evaluate(tokens: list[str]) -> Fraction:
    """Evaluate a fully parenthesized expression given as a list of tokens.

    Tokens are "(", ")", one of + - * /, or a number. Left parentheses may
    be left out. Cost: O(n) time and O(d) space for nesting depth d.
    Precondition: the tokens form a fully parenthesized expression.
    Raises ValueError if the stacks show that the input is not well formed.
    """
    vals: list[Fraction] = []  # @line L1
    ops: list[str] = []
    for t in tokens:  # @line L2
        if t == "(":  # @line L3
            continue
        elif t in OPS:  # @line L4
            ops.append(t)
        elif t == ")":  # @line L5
            if not ops or len(vals) < 2:
                raise ValueError("unbalanced ')'")
            op, b, a = ops.pop(), vals.pop(), vals.pop()  # @line L6
            vals.append(OPS[op](a, b))  # @line L7
        else:
            vals.append(Fraction(t))  # @line L8
    if len(vals) != 1 or ops:
        raise ValueError("not a fully parenthesized expression")
    return vals.pop()  # @line L9

test_dijkstra_two_stack_evaluation.py 52 lines

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/dijkstra-two-stack-evaluation/. The authors are listed in prov/9KN9AK.jsonl.

import random
from fractions import Fraction

import pytest

from dijkstra_two_stack_evaluation import evaluate


def test_page_example() -> None:
    e = "( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )".split()
    assert len(e) == 17
    assert evaluate(e) == 101
    assert evaluate("1 + 2 + 3 ) * 4 * 5 ) ) )".split()) == 101


def test_order_of_operands() -> None:
    assert evaluate("( 7 - 2 )".split()) == 5
    assert evaluate("( 7 / 2 )".split()) == Fraction(7, 2)
    assert evaluate(["42"]) == 42


def test_malformed() -> None:
    with pytest.raises(ValueError):
        evaluate("( 1 + 2 * 3 )".split())
    with pytest.raises(ValueError):
        evaluate("1 + 2 ) )".split())
    with pytest.raises(ValueError):
        evaluate([])


def build(rng: random.Random, depth: int) -> tuple[list[str], Fraction]:
    if depth == 0 or rng.random() < 0.3:
        x = rng.randrange(1, 10)
        return [str(x)], Fraction(x)
    op = rng.choice("+-*/")
    left, a = build(rng, depth - 1)
    right, b = build(rng, depth - 1)
    if op == "/" and b == 0:
        op = "+"
    v = {"+": a + b, "-": a - b, "*": a * b, "/": a / b if b else a}[op]
    return ["("] + left + [op] + right + [")"], v


def test_random_against_recursive_value() -> None:
    rng = random.Random(1961)
    for _ in range(800):
        toks, v = build(rng, rng.randrange(0, 6))
        assert evaluate(toks) == v
        assert evaluate([t for t in toks if t != "("]) == v

What the next level needs

the tests did not run in this build

Read the full page about Dijkstra's two-stack expression evaluation