# BrainFuck part 10 - RPN calc tool

## Welcome!

Welcome to this new playground about the BF language. Make sure you already read

- Getting started with BrainFuck
- BrainFuck part 2 - Working with arrays
- BrainFuck part 3 - Write a BF interpreter in BF
- BrainFuck part 4 - Advanced maths
- BrainFuck part 5 - Math sequences
- BrainFuck part 6 - 16-bit integers
- BrainFuck part 7 - Quine (+ some non-BF quine theory)
- BrainFuck part 8 - JS/C#/BF Multi quine
- BrainFuck part 9 - Sort arrays with Bubble and QuickSort

playgrounds if you didn't already !

The goal of this playground is to implement a calc tool based on reverse polish notation (RPN), and to add extensions on our tool by iterations.

## What is RPN ?

If you owned a calculator manufactured by the Hewlett-Packard company since the 70s, then you can probably skip this section.

The reverse polish notation is a mathematical notation where operators follows operands.

Let's consider operation `(6 + 2) x 3 - 1 x (5 x 4)`

. Result is 4.

- Evaluation of block
`6 + 2`

with operands 6 and 2, and operator + - Evaluation of block
`5 x 4`

with operands 5 and 4, and operator x - Evaluation of block
`8 x 3`

- Evaluation of block
`1 x 20`

**prior to subtraction** - Evaluation of block
`24 - 20`

The notation is easy to understand, but it's evaluation is less easy to implement : we need to find the priority between blocks, operators, ...

Then comes the **Polish notation (PN)**. The same operation becomes

```
- x + 2 6 3 x 1 x 5 4
```

Not so easy to read, right ? Let's try anyway

- minus applies on the next 2 operands
- multiply applies on the next 2 operands
- plus applies on the next 2 operands
- 2
- 6

- 6+2 = 8
- 3

- plus applies on the next 2 operands
- 8x3 = 24
- multiply applies on the next 2 operands
- 1
- multiply applies on the next 2 operands
- 5
- 4

- 5x4 = 20

- 1x20 = 20

- multiply applies on the next 2 operands
- 24-20 = 4

This notations allows to get rid of parentheses, though it's not really easy to read.

And unfortunately, it's also not really easy to interpret : the subtraction was initiated a large number of steps before its computation.

Now, let's look at the **Reverse polish notation(RPN)**. The operator follows the operands

```
6 2 + 3 x 1 5 4 x x -
```

Implementation of an RPN evaluator is quite easy, using a stack-based automaton.

*empty stack*- Push 6
*[ 6 ]* - Push 2
*[ 6 , 2 ]* **Add***[ 8 ]*- Push 3
*[ 8, 3 ]* **Mult***[ 24 ]*- Push 1
*[ 24, 1 ]* - Push 4
*[ 24, 1, 4 ]* - Push 5
*[ 24, 1, 4, 5 ]* **Mult***[ 24, 1, 20 ]***Mult***[ 24, 20 ]***Sub***[ 24 ]*

In other words, an operand is pushed on the stack, and an operator pops operand 2 and operand 1 (in this order) from the stack.

Now, let's implement a BF stack-based RPN evaluator automaton.