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
  • 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 ]
• 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.