Back
Close

BrainFuck part 10 - RPN calc tool

DPAmar
13.2K views

Welcome!

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

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.

Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.
Go to tech.io