Goal: Create an RPN calculator

In this exercise, you’ll implement a simple calculator using Reverse Polish Notation (RPN).

You will likely be most familiar to algebraic notation, or infix notation, so first read about RPN first to get an idea of what it is and why it’s easy to implement an interpreter for it. It will take a bit of getting used to RPN before really appreciating it.

The “trick” behind RPN calculators: a stack

Each operand is pushed onto the stack, each operator will pop the operands it needs off the stack and pushes its result back onto the stack. It never needs more than two memory cells.

We’ll keep it simple

For the sake of keeping the end result under ±250 lines of code, we’ll keep it simple:

• Support for base 10 signed integer math only,
• Support for the basic math operations: + / - / * / / / %

Version 00: Application setup

As a first basic step, implement a program to test your build setup.

It doesn’t have to be functional otherwise.

Create a new binary executable project using cargo.

Version 01: Reading from standard input

Add the code to read a string of user input from the command-line terminal.

In the best case, your program can accept any data from “standard input”.

This can be used for testing:

Version 02: Input data tokenization and parsing

Add the code to categorize the input string. Classify the code input data as either:

• An operand (i.e. signed integer numbers),
• An operator (i.e. one of the supported operation symbols),
• Invalid data.

Version 03: Functions for tokenization / parsing

In this step, we’ll move the code out of fn main, and create a separate function for it.

Carefully design the function API, and consider argument/return types, error handling and tests.

Hint: The solution code uses an impl Trait argument type to make the function as generic as possible. This not only improves reuse possibilities, but also facilitates testing. Read about it here and here.

Version 04: Calculation support

Add the code to perform a single calculation using the parsed and tokenized user input.

Version 05: Operand/result memory

Add the code for proper stack-based memory to store operands and results.

Version 06: State machine setup

In order to support longer calculations, like \(7 \space 21 \space * \space 9 \space -\), we must implement a state machine.

The result of each calculation is stored on the stack, as if it were the first operand. We also need a way to detect the calculation end, which will influence the behavior of the calculator.

Again, make sure errors are handled properly. Input/calculation errors are not fatal errors (i.e. not panics), and must be handled separately.

Version 07: Improving robustness

Find situations where calculations fail, and add code to remediate / gracefully fail.

For example, what happens if we enter:

• \(1 \space 0 \space /\)
• \(999999999999999999999999999 \space 1 \space +\)

Version 08: Reorganizing and documentation

Let’s reorganize our code into library components (types/methods/functions), and an executable (fn main).

Keep the function unit tests local to the functions, or move them to the /tests directory.

Also add documentation for all library components. Make sure your documentation features example code, that is tested when running cargo test.

Version 09: Iterator adaptor for token reading

In the RPN calculator, the state machine simply keeps on reading from the token source, until the end of the token stream is reached. This “sequence source”-like behavior sounds very much like how we would work with iterators. Would it be possible to build an iterator type around the read_token function? Let’s find out!

Read about iterators here and here. Be sure to deal with errors correctly; writing the iterator itself is easy, error handling makes it more tricky. Good luck!