BrainFuck part 10 - RPN calc tool

DPAmar
13.2K views

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content

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.

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content