If you try to make a enum type that uses itself as a field in one of its variants, then the type will potentially have an infinite size. And if you would try to make a local variable of that type, the compiler wouldn't know how big the stack frame for that function would have to be. To avoid this we introduce an indirection via a Box wrapper. It forces the wrapped portion of the type to be heap-allocated, and the size of Box itself becomes predictable.

Box is not the only type you can use for this purpose. Rc and Arc are other examples of these smart pointer types. And in addition, Vec from standard library holds all its items on a heap, too.

We offer a rough scaffold for the parse function in the starter code. As we split the input around spaces we will get either a number or an operator at a time. We will use stack variable to store temporary sub-expressions.

When we encounter an operator we pop one or two expressions from the stack, wrap them into a new expression, and then push the it back to the stack. When we encounter a number we simply wrap it into Expr::Number(...) and push it.

At the end, if the original string was well-formed we should end up with just a single item in the stack representing the whole expression.

To parse numbers you can use the parse() method on string slices. This method can produce values of many different types, and you can use turbofish syntax to give the compiler a hint about what kind of value you expect:

let value = "12".parse::<i64>()?;

In the parse function there are many instances where you either get an Option or an Result with an error that is different from ParseError. While calling unwrap() in these cases can be tempting there are better options.

In general, unless there's some way you can recover from an error in your function you should prefer ? operator to bail out of it when things go wrong. Thus, when getting an Option or a Result your first though should be: "I want to use ?. How do I get there?"

Thankfully, Result has a convenient map_err method that can convert the error you get into an error type that you need:

file.read_to_string(&mut buffer).map_err(|io_error| MyError::IoVariant)?;

Likewise, Option has a helpful ok_or method to convert to Result type that you can then use ? on.

100_u8.checked_add(200_u8).ok_or(MyError::ByteOverflow)?;

Option and Result have many other useful methods, and given that these types show up in Rust code all the time learning their API will help you writing more terse and idiomatic code. You can read more about them in Item 3 of Effective Rust book.

In addition, you can always match / let else / if let on your Options and Results in tricky situations.

While the use of panicking functions like unwrap in production code is often frowned upon they are popular for tests. Similar to how you can use unwrap to get a value out of Ok variant of a Result you can use unwrap_err to get a value out of Err. Here's an example:

#[test]
fn no_a_number() {
    let input = "X";
    let error = parse(input).unwrap_err();
    assert_eq!(error, ParseError::NotANumber);
}

Rust's testing macroassert_eq! compares the two arguments using == operator and if the values do not match it prints them in Debug mode to show you the difference between them. Thus, to use it with your types like Expr the types have to be comparable and printable, i.e. implement Debug and PartialEq traits. Thankfully, both traits can usually be derived automatically like so:

#[derive(Debug, PartialEq)]
pub enum Expr {
    // ...
}

The eval function takes &Expr type as an argument and when you use it in match you will get &i64 instead of i64. You can use a dereferencing operator * to convert a reference to a number to a number itself:

// expr: &Expr
match expr {
    // n: &i64
    Expr::Number(n) => {
        let x: i64 = *n;
    }
}

Rust will make this conversion automatically, you don't have to do anything! To learn more about how it works read about Deref coercion in The Rust Book.

Similar to &i64 to i64 you can use a dereferencing operator:

let boxed_expression: Box<Expr> = Box::new(Expr::Number(1));
let expr: Expr = *boxed_expression;

Step 1: Make a new library

cargo new --lib calc

Paste the starting code into lib.rs. Add #[derive(Debug, PartialEq)] for Expr and error types to fix compilation errors in the test.

Step 2: Add support for numbers

Let's start with parse function. Inside a for loop we'll be matching word variable against different operators. If none of the operators match we will assume that we encounter a number. So, number parsing will be in the default branch of our match expression:

// inside `parse`
for word in input.split_ascii_whitespace() {
    match word {
        "+" => todo!("add support for different operators"),
        _ => {
            let number = word
                .parse::<i64>()
                .map_err(|_| ParseError::NotANumber(word.to_string()))?;
            let expr = Expr::Number(number);
            stack.push(expr);
        }
    }
}

Tip: You can use Rust Analyzer to populate enum types. When you type ParseError::NotANumber(word.to_string()) put the cursor over NotANumber and use Generate Variant quick action. You can do it again after typing Expr::Number.

Now, let's work on eval function. After you type match expr in the body you once again can use a quick action to generate a missing match arm for Number variant.

// in `eval`
match expr {
    Expr::Number(n) => Ok(*n),
}

You can now run the number test that we provide.

You can also write an error text for ParseError::NotANumber:

// in `tests` module:
#[test]
fn not_a_number() {
    let input = "X";
    let error = parse(input).unwrap_err();
    assert_eq!(error, ParseError::NotANumber("X".to_string()));
}

Step 3: Add support for addition

You can start with any operator of your choosing. Some of them may be trickier than others:

• sqr takes only one argument
• - and / take the order of the operands in account
• / can produce an error during evaluation

So, depending on what operator we will implement first our work can be easier (sqr) or harder (/). Addition seems like a good starting place.

parse:

match word {
    "+" => {
        let a = stack.pop().ok_or(ParseError::MissingOperand)?;
        let b = stack.pop().ok_or(ParseError::MissingOperand)?;
        let a = Box::new(a);
        let b = Box::new(b);
        let expr = Expr::Add(a, b);
        stack.push(expr);
    }
    _ => {
        // number parsing code
    }
}

Once again: use Generate Variant for the new kind of expression.

eval:

match expr {
    Expr::Number(n) => Ok(*n),
    Expr::Add(a, b) => {
        let a = eval(a)?;
        let b = eval(b)?;
        Ok(a + b)
    }
}

and tests:

#[test]
fn add() {
    let input = "40 2 +";
    let expr = parse(input).unwrap();
    let value = eval(&expr).unwrap();
    assert_eq!(value, 42);
}

Step 4: Add support for squaring a number

You can probably notice that both parse and eval functions open opportunities for a refactoring. Before doing that we should probably explore the variant of expression with the largest potential of being different. sqr operator will produce code of a different shape due to it requiring only a single operand. In real world situations it is sometimes hard to predict how different requirements will shape the resulting code. However, making an attempt at a prediction like this can help you with avoiding refactoring prematurely and having to rollback massive changes later.

parse:

match word {
    "+" => {
        // ...
    }
    "sqr" => {
        let a = stack.pop().ok_or(ParseError::MissingOperand)?;
        let a = Box::new(a);
        let expr = Expr::Square(a);
        stack.push(expr);
    }
    _ => {
        // ...
    }
}

eval:

match expr {
    // ...
    Expr::Square(a) => {
        let a = eval(a)?;
        Ok(a.pow(2))
    }
}

Test:

#[test]
fn square() {
    let input = "5 sqr";
    let expr = parse(input).unwrap();
    let value = eval(&expr).unwrap();
    assert_eq!(value, 25);
}

Step 5: Refactoring

parse function

Some observations:

• Every branch of our big match statement ends up producing an expression.
• Every time we pop expressions from the stack we have to box them.

So, here's a plan:

• Let's make match produce an expression: let expr = match word { ... };
• Let's change our stack variable to store Boxed expressions

pub fn parse(input: &str) -> Result<Expr, ParseError> {
    let mut stack: Vec<Box<Expr>> = Vec::new();
    for word in input.split_ascii_whitespace() {
        let expr = match word {
            "+" => {
                let a = stack.pop().ok_or(ParseError::MissingOperand)?;
                let b = stack.pop().ok_or(ParseError::MissingOperand)?;
                Expr::Add(a, b)
            }
            "sqr" => {
                let a = stack.pop().ok_or(ParseError::MissingOperand)?;
                Expr::Square(a)
            }
            _ => {
                let number = word
                    .parse::<i64>()
                    .map_err(|_| ParseError::NotANumber(word.to_string()))?;
                Expr::Number(number)
            }
        };
        stack.push(Box::new(expr));
    }
    assert_eq!(stack.len(), 1);
    let res = stack.pop().unwrap();
    Ok(*res)
}

Note that we have to adjust the type from Box<Expr> to Expr at the end. While we are at it let's rewrite the end portion of the function to get rid of an assertion and an unwrap:

for word in input.split_ascii_whitespace() {
    // ...
}

match stack.pop() {
    Some(expr) if stack.is_empty() => Ok(*expr),
    Some(_) => Err(ParseError::TooManyOperands),
    None => Err(ParseError::EmptyInput),
}

Let's test our new error conditions:

#[test]
fn too_many_operands() {
    let input = "42 42 42 +";
    let error = parse(input).unwrap_err();
    assert_eq!(error, ParseError::TooManyOperands);
}

#[test]
fn empty_input() {
    let input = "      ";
    let error = parse(input).unwrap_err();
    assert_eq!(error, ParseError::EmptyInput);
}

eval function

So far every branch of the match produces an number that we later wrap into Ok.

pub fn eval(expr: &Expr) -> Result<i64, EvalError> {
    let value = match expr {
        Expr::Number(n) => *n,
        Expr::Add(a, b) => eval(a)? + eval(b)?,
        Expr::Square(a) => eval(a)?.pow(2),
    };
    Ok(value)
}

Step 6: Subtraction

In parse function all subsequent operators will require two stack.pop() calls. We may as well combine different operators together and use unreachable! macro for the second match:

match word {
    "+" | "-" => {
        let a = stack.pop().ok_or(ParseError::MissingOperand)?;
        let b = stack.pop().ok_or(ParseError::MissingOperand)?;
        match word {
            "+" => Expr::Add(a, b),
            "-" => Expr::Sub(a, b),
            _ => unreachable!(),
        }
    }
    // ...
}

// in `eval`
match expr {
    // ...
    Expr::Add(a, b) => eval(a)? + eval(b)?,
    Expr::Sub(a, b) => eval(a)? - eval(b)?,
    // ...
};

#[test]
fn sub() {
    let input = "42 2 -";
    let expr = parse(input).unwrap();
    let value = eval(&expr).unwrap();
    assert_eq!(value, 40);
}

Adding a test will reveal that we have a bug with the order of operands.

---- tests::sub stdout ----
thread 'tests::sub' panicked at calculator/src/lib.rs:96:9:
assertion `left == right` failed
  left: -40
  right: 40

It's up to you to decide where to mitigate the issue. You can do it in eval or in parse. We will do it in parse right away by popping b from the stack first:

match word {
    "+" | "-" => {
        let b = stack.pop().ok_or(ParseError::MissingOperand)?;
        let a = stack.pop().ok_or(ParseError::MissingOperand)?;
        // ...
    }
    // ...
}

Step 7: Multiplication

The changes will completely match code for addition and subtraction.

Here's a test for you to check your work:

#[test]
fn mul() {
    let input = "21 2 *";
    let expr = parse(input).unwrap();
    let value = eval(&expr).unwrap();
    assert_eq!(value, 42);
}

Step 8: Division

Division will require more code in the eval function to check if the divisor is Zero. You can perform the check inside the Expr::Div arm or move it to its own arm and use a guard expression like this:

match expr {
    // ...
    Expr::Div(_, divisor) if eval(&divisor)? == 0 => {
        return Err(EvalError::DivisionByZero)
    }
    Expr::Div(a, b) => eval(a)? / eval(b)?,
    // ...
}

Let's test our code:

#[test]
fn div() {
    let input = "84 2 /";
    let expr = parse(input).unwrap();
    let value = eval(&expr).unwrap();
    assert_eq!(value, 42);
}

#[test]
fn divide_by_zero() {
    let input = "42 0 /";
    let expr = parse(input).unwrap();
    let error = eval(&expr).unwrap_err();
    assert_eq!(error, EvalError::DivisionByZero);
}

Finally, you can uncomment the smoke test and see how our library works for complex expressions.

You can find a complete solution in our repository.