Recursive types need indirection: E0072

Evaluate a prefix expression containing integers, negation, addition and division. Repair the recursive type in the starter, update its parser constructors, and implement the evaluator.

pub fn eval(expr: String) -> String

Syntax and output

expr := integer
      | (neg expr)
      | (add expr expr)
      | (div expr expr)

Operators are lowercase and case-sensitive. neg takes one operand; add and div take two. Parentheses are separate tokens even when they touch another token. Other tokens must be separated by whitespace. The supplied parser uses Rust's Unicode-aware split_whitespace, so spaces, tabs and newlines are accepted, including around the whole expression.

An integer token contains ASCII decimal digits with an optional leading + or - and must fit in i64. Leading zeros are allowed. Underscores, hexadecimal notation, non-ASCII digits and out-of-range literals are syntax errors. The whole input must contain exactly one expression. Empty input, unknown operators, wrong operand counts and leftover tokens are also syntax errors.

Return a decimal integer without a leading plus or unnecessary zeros, or one of these exact error strings:

Parse the entire input before evaluating it. During evaluation, evaluate the left child before the right child and return the first error encountered. Only perform a node's operation after its children have succeeded.

For example, (div -7 2) returns -3: integer division truncates toward zero. (add (div 1 0) (neg -9223372036854775808)) returns error: divide by zero, since the left child fails first. Adding a trailing token to that input instead produces error: syntax before evaluation starts.

Why the recursive enum does not fit

In the starter, Neg(Expr) contains another complete Expr inline, and Add(Expr, Expr) contains two. Determining the storage for one value requires the same calculation again for each child. Rust rejects this definition with E0072 because it has no finite-sized inline representation.

Put the recursive children behind Box<Expr> instead. A box for a sized type is represented by one pointer; the child lives in separate storage. This breaks the circular size dependency. It does not prescribe an exact byte count for the enum: alignment, target pointer size and enum layout still matter.

Change all recursive child fields, including Neg's single child. Then wrap the parsed children in Box::new at the construction sites. Finally, replace the evaluator's todo!(). The compiler may report a related cycle diagnostic such as E0391 alongside E0072; the exact set of messages can vary with the code and compiler version.

Boxing makes each node finite-sized, but does not make recursion unlimited. The parser, evaluator and automatic tree destruction can still use stack space proportional to nesting depth. The tests include a 50-level chain; this exercise does not require handling arbitrary resource-exhausting input.

Borrowing a boxed child

Matching a borrowed tree gives you borrowed children. A &Box<Expr> can coerce to &Expr, so a recursive evaluator can borrow each child without taking ownership or cloning it.

This smaller, complete tree example counts nodes. It illustrates the same borrowing pattern without implementing the arithmetic evaluator:

enum Tree {
    Leaf,
    Branch(Box<Tree>, Box<Tree>),
}

fn nodes(tree: &Tree) -> usize {
    match tree {
        Tree::Leaf => 1,
        Tree::Branch(left, right) => 1 + nodes(left) + nodes(right),
    }
}

fn main() {
    let tree = Tree::Branch(
        Box::new(Tree::Leaf),
        Box::new(Tree::Branch(Box::new(Tree::Leaf), Box::new(Tree::Leaf))),
    );
    assert_eq!(nodes(&tree), 5);
    assert_eq!(nodes(&tree), 5); // The first call only borrowed the tree.
}

You can also borrow a box's contents explicitly with &*boxed. Moving a non-Copy value out with *boxed requires ownership of the box. These are different operations; borrowing the contents does not move them out. Ordinary enum matching and dereference coercion are enough for this task.

Checked arithmetic gives consistent errors

Use checked_neg, checked_add and checked_div, which return None when the requested result cannot be represented. This makes the behavior explicit instead of depending on compiler overflow-check settings.

Division needs one extra distinction. After both operands evaluate successfully, test whether the divisor is zero and return DivByZero if it is. Otherwise, a failed checked_div means overflow, including i64::MIN / -1. Negating i64::MIN also overflows.

An out-of-range literal is a parsing failure, not arithmetic overflow. Preserve the parser's whole-input check and its mapping to EvalErr::Syntax while repairing the constructors. Submissions must compile, pass the test cases and pass the runner's Clippy checks.