Abstract Syntax Trees

Once you have tokens, the parser groups them into a tree that reflects the expression's actual structure — the Abstract Syntax Tree (AST). This is where operator precedence gets encoded: 1 + 2 * 3 must parse so that 2 * 3 is evaluated as a single unit before being added to 1, which means the AST has to nest the multiplication INSIDE the addition, not the other way around.

def parse(tokens):
    pos = [0]
    def peek():
        return tokens[pos[0]] if pos[0] < len(tokens) else None
    def advance():
        tok = tokens[pos[0]]
        pos[0] += 1
        return tok
    def parse_factor():
        tok = advance()
        if tok == "(":
            node = parse_expr()
            advance()  # consume ")"
            return node
        return tok
    def parse_term():
        node = parse_factor()
        while peek() in ("*", "/"):
            op = advance()
            node = (op, node, parse_factor())
        return node
    def parse_expr():
        node = parse_term()
        while peek() in ("+", "-"):
            op = advance()
            node = (op, node, parse_term())
        return node
    return parse_expr()

Evaluating an AST is a direct recursive walk: a leaf (a plain number) is already its own value; an internal node is "evaluate both children, then apply the operator." This same recursive-tree-walk shape reappears constantly — it's exactly how Data Structures' trees-bsts module walks a binary search tree, just applied to compute a result instead of searching for a key.