Recursive types need indirection: E0072

Evaluate a fully-parenthesised prefix expression.

pub fn eval(expr: String) -> String

The grammar is four rules:

expr := <i64>
      | ( neg expr )
      | ( add expr expr )
      | ( div expr expr )

Return the value rendered in decimal, or one of exactly three error strings: "error: syntax", "error: divide by zero", "error: overflow". Division truncates toward zero, the way Rust’s / does — (div -7 2) is -3.

A parser is supplied. Two things are not: a type that can hold the tree, and the evaluator.

The first compile error that is about memory, not borrowing

Every error you have met so far has been about who may touch what, when. This one is different. Write the obvious enum:

enum Expr {
    Num(i64),
    Neg(Expr),
    Add(Expr, Expr),
    Div(Expr, Expr),
}

and rustc says E0072: recursive type Expr has infinite size. Not “this is a bad idea” — infinite size, as a matter of arithmetic. The compiler lays out an enum as a tag plus the largest variant. How large is Add? Two Exprs. How large is an Expr? At least as large as Add. There is no number that satisfies that equation except infinity, so there is no stack frame that can hold one.

Expect two errors, not one. E0072 usually arrives paired with E0391, “cycle detected when computing whether Expr needs drop” — the drop-glue computation runs into the same loop for the same reason. Both disappear together when you fix the layout.

The fix is the one rustc suggests: put the children behind a pointer. A Box<Expr> is one word wide no matter what it points at, so Add becomes two words plus a tag, and the equation closes. Note that the recursion has not gone away — the type is still recursive, and the tree is still arbitrarily deep. What changed is that each node now has a fixed, knowable size.

You will need to update the parser’s three construction sites to wrap their children in Box::new. That is the whole edit.

Matching on the boxes

In the evaluator, matching &Expr binds the children as &Box<Expr>. Calling eval_expr(inner) just works, because &Box<Expr> coerces to &Expr — the deref coercion doing quiet work again.

What you cannot do is destructure the box itself: Expr::Add(box l, box r) is box patterns, which are still unstable (E0658, “box pattern syntax is experimental”) and have been for a decade. When you genuinely need the value out of a box rather than a reference to it, match &*b { … } or *b is the answer.

Nullable links: Option<Box<T>>, not Box<Option<T>>

You do not need it here, but you will tomorrow. The idiomatic “maybe a next node” is Option<Box<T>>, and it is free: the compiler knows a Box can never be null, so it stores None as the all-zeroes pointer. Option<Box<T>> is the same eight bytes as Box<T>. Box<Option<T>> allocates unconditionally and then still needs a discriminant inside the allocation. Same words, opposite cost.

About cons lists

Most tutorials teach this with enum List { Cons(i32, Box<List>), Nil }. Be clear about what that is: a teaching device, not a data structure you should build. A linked list scatters every element across the heap, defeats the prefetcher, allocates once per element and cannot be iterated in cache order — clippy has a lint, linkedlist, whose entire message is “a VecDeque might work better”. Rust’s own std::collections::LinkedList documentation opens by telling you to use Vec or VecDeque instead.

Trees are the honest use of this shape, which is why this problem is a tree. Every AST, every parser, every interpreter you write starts exactly here.

Arithmetic

Remember that submissions are compiled with -O, so overflow checks are off and a + b wraps silently. checked_add, checked_neg and checked_div return Option, and turning None into EvalErr::Overflow is how the overflow cases pass. One subtlety: checked_div returns None for both a zero divisor and i64::MIN / -1, and this problem wants those distinguished — test the divisor yourself before dividing.