# BrainFuck part 10 - RPN calc tool

DPAmar
1,935 views

## Welcome!

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
• 8x3 = 24
• multiply applies on the next 2 operands
• 1
• multiply applies on the next 2 operands
• 5
• 4
• 5x4 = 20
• 1x20 = 20
• 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 ]
• 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.