Design a boolean and arithmetic expression library

01The design, in the six-step framework

1. Requirements and use cases

A developer passes text such as a & (b | c) or 2 * (x + 1) to a library and gets back an expression object. They can evaluate it against a set of variable values many times, simplify it (x & true becomes x, 2 * 3 becomes 6), and add new operations later. Bad input is rejected with a position.

Out of scope: user-defined functions, types beyond integers and booleans, and a full type checker. In one reported L4 round the candidate was asked only for class and API declarations, so be ready to stop at section 3 and defend the shape.

Constraints: one parsed tree is reused for many evaluations, so trees are immutable and shareable across threads; new operations must not edit every node class; evaluation of & and | must short-circuit, so an unbound variable on the unused side is not an error.

2. Core entities and relationships

• Expr: the abstract node with a single accept method. Const, Var, Unary and Binary are its four frozen subclasses.
• Visitor: an abstract operation over the tree with one method per node type.
• Evaluator: a visitor holding the variable environment; Simplifier: a visitor that returns a new tree.
• parse with its private _Parser: text to tree, using precedence levels. ExprError carries the offset.

Unary and Binary compose child expressions, which makes the tree a composite: a single number and a huge formula are the same type. All four node classes inherit from Expr.

3. Interfaces and key methods

class Expr(ABC):
    @abstractmethod
    def accept(self, visitor: "Visitor[T]") -> T: ...

class Visitor(ABC, Generic[T]):
    def visit_const(self, e: "Const") -> T: ...
    def visit_var(self, e: "Var") -> T: ...
    def visit_unary(self, e: "Unary") -> T: ...
    def visit_binary(self, e: "Binary") -> T: ...

def parse(text: str) -> Expr:
    """'a & (b | !c)' or '2 * (x + 1)'; raises ExprError with the offset."""

class Evaluator(Visitor[object]):
    def __init__(self, env: Mapping[str, object]) -> None: ...

class Simplifier(Visitor[Expr]): ...      # returns a new, smaller tree
class Printer(Visitor[str]): ...          # fully parenthesised text

Invariants: nodes never change after construction; simplify preserves meaning, so for every environment that binds all variables, evaluating the simplified tree equals evaluating the original; accept dispatches to exactly the visitor method for the node's type.

4. Design patterns and the choices behind them

Composite for the tree

Expressions nest to any depth. Representing them as a tree of one abstract type means an operation written for Expr works on any size of input. Polymorphism replaces a chain of type checks, and an abstract interface is what callers depend on.

Visitor for the operations

Here the node types are nearly fixed while operations keep arriving: evaluate, simplify, print, collect variables, compile. Putting an evaluate method on each node means editing four classes per new operation. A visitor puts each operation in one class. The trade-off runs the other way if a new node type appears: every visitor must change. An abstract base with abstract methods makes that failure loud at construction. If the interviewer says new node types are the likely change, drop the visitor and use a plain evaluate method; say which change you are optimising for.

Precedence levels in a table

Recursive descent usually needs one method per precedence level. A single binary(level) method driven by the LEVELS table removes that repetition, and left associativity comes from the while loop. Adding an operator is a table edit (see parsing and tokenizing).

Short-circuit lives in the Evaluator

Logical operators are handled before the arithmetic table because their right side must stay unevaluated when the left decides the result. Evaluating both sides first would raise on an unbound variable that the expression never needs.

5. Core flow and code

1. parse("x & (true | y)"): the tokenizer produces tokens with offsets; binary(0) descends to atoms and builds Binary("&", Var("x"), Binary("|", Const(True), Var("y"))).
2. tree.accept(Simplifier()): the inner Binary sees Const(True) under | and returns Const(True).
3. The outer Binary now has x & true and returns Var("x").
4. simplified.accept(Evaluator({"x": False})) dispatches to visit_var and returns False. The unbound y no longer exists in the simplified tree.
5. parse("2 *") reaches atom with no token and raises ExprError at offset 3.

from __future__ import annotations
import re
from abc import ABC, abstractmethod
from dataclasses import dataclass
from typing import Generic, Mapping, TypeVar

T = TypeVar("T")

class ExprError(Exception):
    def __init__(self, msg: str, pos: int) -> None:
        super().__init__(f"{msg} at offset {pos}"); self.pos = pos

class Expr(ABC):
    @abstractmethod
    def accept(self, visitor: "Visitor[T]") -> T: ...

@dataclass(frozen=True)
class Const(Expr):
    value: object
    def accept(self, v): return v.visit_const(self)

@dataclass(frozen=True)
class Var(Expr):
    name: str
    def accept(self, v): return v.visit_var(self)

@dataclass(frozen=True)
class Unary(Expr):
    op: str
    arg: Expr
    def accept(self, v): return v.visit_unary(self)

@dataclass(frozen=True)
class Binary(Expr):
    op: str
    left: Expr
    right: Expr
    def accept(self, v): return v.visit_binary(self)

class Visitor(ABC, Generic[T]):
    @abstractmethod
    def visit_const(self, e: Const) -> T: ...
    @abstractmethod
    def visit_var(self, e: Var) -> T: ...
    @abstractmethod
    def visit_unary(self, e: Unary) -> T: ...
    @abstractmethod
    def visit_binary(self, e: Binary) -> T: ...

OPS = {"+": lambda a, b: a + b, "-": lambda a, b: a - b, "*": lambda a, b: a * b, "/": lambda a, b: a / b}

class Evaluator(Visitor[object]):
    def __init__(self, env: Mapping[str, object]) -> None:
        self.env = env
    def visit_const(self, e: Const) -> object: return e.value
    def visit_var(self, e: Var) -> object:
        if e.name not in self.env:
            raise KeyError(f"unbound variable {e.name}")
        return self.env[e.name]
    def visit_unary(self, e: Unary) -> object:
        val = e.arg.accept(self)
        return (not val) if e.op == "!" else -val
    def visit_binary(self, e: Binary) -> object:
        if e.op == "&":                                   # short-circuit: right may be unbound
            return bool(e.left.accept(self)) and bool(e.right.accept(self))
        if e.op == "|":
            return bool(e.left.accept(self)) or bool(e.right.accept(self))
        return OPS[e.op](e.left.accept(self), e.right.accept(self))

class Simplifier(Visitor[Expr]):
    def visit_const(self, e: Const) -> Expr: return e
    def visit_var(self, e: Var) -> Expr: return e
    def visit_unary(self, e: Unary) -> Expr:
        arg = e.arg.accept(self)
        if isinstance(arg, Const):
            return Const(Evaluator({}).visit_unary(Unary(e.op, arg)))
        if e.op == "!" and isinstance(arg, Unary) and arg.op == "!":
            return arg.arg                                # !!x -> x
        return Unary(e.op, arg)
    def visit_binary(self, e: Binary) -> Expr:
        l, r = e.left.accept(self), e.right.accept(self)
        if isinstance(l, Const) and isinstance(r, Const):
            return Const(Evaluator({}).visit_binary(Binary(e.op, l, r)))
        if e.op == "&" and (Const(False) in (l, r)): return Const(False)
        if e.op == "|" and (Const(True) in (l, r)): return Const(True)
        if e.op == "&": 
            if l == Const(True): return r
            if r == Const(True): return l
        if e.op == "|":
            if l == Const(False): return r
            if r == Const(False): return l
        return Binary(e.op, l, r)

TOKEN = re.compile(r"\s*(\d+|[A-Za-z_]\w*|[-+*/()!&|])")
LEVELS = [("|",), ("&",), ("+", "-"), ("*", "/")]     # lowest precedence first

class _Parser:
    def __init__(self, text: str) -> None:
        self.toks, pos = [], 0
        text = text.rstrip()
        while pos < len(text):
            m = TOKEN.match(text, pos)
            if not m:
                raise ExprError("bad character", pos)
            self.toks.append((m.group(1), m.start(1))); pos = m.end()
        self.i, self.end = 0, len(text)

    def peek(self) -> str | None:
        return self.toks[self.i][0] if self.i < len(self.toks) else None

    def take(self) -> str:
        self.i += 1
        return self.toks[self.i - 1][0]

    def binary(self, level: int) -> Expr:
        if level == len(LEVELS):
            return self.unary()
        left = self.binary(level + 1)
        while self.peek() in LEVELS[level]:
            left = Binary(self.take(), left, self.binary(level + 1))
        return left

    def unary(self) -> Expr:
        if self.peek() in ("!", "-"):
            op = self.take()
            return Unary(op, self.unary())
        return self.atom()

    def atom(self) -> Expr:
        tok = self.peek()
        pos = self.toks[self.i][1] if tok else self.end
        if tok is None:
            raise ExprError("unexpected end", pos)
        self.take()
        if tok == "(":
            inner = self.binary(0)
            if self.peek() != ")":
                raise ExprError("expected )", pos)
            self.take()
            return inner
        if tok.isdigit(): return Const(int(tok))
        if tok in ("true", "false"): return Const(tok == "true")
        if tok[0].isalpha() or tok[0] == "_": return Var(tok)
        raise ExprError(f"unexpected {tok!r}", pos)

def parse(text: str) -> Expr:
    p = _Parser(text)
    tree = p.binary(0)
    if p.peek() is not None:
        raise ExprError(f"trailing {p.peek()!r}", p.toks[p.i][1])
    return tree

6. Extensions, concurrency and what interviewers probe

• Declarations only: the reported round wanted classes and signatures. Section 3 is that answer; explain immutability and accept, then offer to implement one operation.
• Collecting variables: a new Variables visitor returning a set; no node changes, which demonstrates the choice in one line.
• Division by zero: Simplifier folds constants through Evaluator, so 1 / 0 raises at simplify time. Decide whether folding should leave such a node alone instead.
• A printer: a Printer visitor that returns fully parenthesised text gives a stable form for logs and for comparing two trees; it is about twenty lines and needs no change to any node class.
• Concurrency: trees are frozen and each Evaluator holds only its environment, so many threads can evaluate one tree with no lock.
• Test first: precedence (1 + 2 * 3 is 7), left associativity (8 - 3 - 2 is 3), short-circuit with an unbound right side, and a property test that simplify preserves the value across random environments.
• Common mistake: an isinstance ladder inside one big evaluate function, which every new node and every new operation must edit.

02Where this question was reported

• raw.githubusercontent.com · Build a streaming CSV importer with row validation; parse and evaluate a simple expression/DSL
• LLD Mastery · Commercial tag: JSON parser (recursive descent, tokenization)
• LeetCode Discuss · Asked to write the classes and APIs as declarations only; design-focused