OpenMediaLib User and Development Guide

Reverse Polish Notation

As a race, humans are conditioned to accept certain complexities via a heady mix of social engineering and indoctrination. Mostly, the effects of this are beneficial, but sometimes they lead us to introducing complex solutions when simpler ones exist.

One example of this is in our traditional notation for arithmetic calculations – we all immediately understand:

1 + 2

We are taught the rules of association, so that for most of us above a certain age, the following is unambiguous:

1 + 2 * 3

We know that the * has a higher order of precedence, so the result is 1 + ( 2 * 3 ), not (1 + 2 ) * 3. In fact, we need the parenthesis to differentiate between those cases, and in truth, it would be more desirable to enforce the parenthesis usage rather than having implied rules, but humans, particularly intelligent ones, tend to laziness.

Like humans, a computer needs to be taught the associative rules in much the same we are, and thus, the complex conditioning continues into the field of computers.

There are alternative notations which don't have the same ambiguity – Reverse Polish Notation (or RPN) is one such approach.

RPN essentially involves a stack of number and operators, so our initial 1 + 2, becomes: 

1 2 +

When parsing, we start on the right and pop the entry – a + operator logically requires 2 numbers, so it in turn pops two numbers (being 2 and 1), adds them together and pushes the result on the stack.

Similarly, 1 + ( 2 * 3 ) becomes: 

1 2 3 * +

The + requires 2 numbers, the first pop results in *, which in turn requires two numbers (2 and 3), leaving 6 as the first operand of the + and 1 is retrieved for the second, thus we get 7.

Our ( 1 + 2 ) * 3 becomes: 

1 2 + 3 *

Thus, there is no ambiguity and no parenthesis are required.

There is, however, one critical rule which must be understood – and remembered – so here is the little bit of indoctrination needed.

The rules of arithmetic dictate that an operator is commutative providing you can apply the terms in any order and get the same result – hence: 

1 + 2 = 2 + 1 
1 * 2 = 2 * 1

show that addition and multiplication are commutative.

By contrast, division and subtraction are not: 

1 / 2 != 2 / 1
1 – 2 != 2 - 1

RPN dictates a single rule – that the left and right terms are presented on the stack in the same order as we do in in-fix, hence: 

1 / 2 = 1 2 /
1 – 2 = 1 2 -

As a final example, consider a maths function like a sine.

Our traditional arithmetic model gives us expressions like: 

sin( x ) + 1

Which we can express in RPN as: 

x sin 1 +

It should be clear by now that the in-fix expression which we use is just one way to represent any particular expression. In fact, many permutations of the representation are possible – for example, we could represent the above in a manner which is similar to a filter graph (with the result being the outer most right hand node): 

x
 \
 sin
   \
    +
   /
  1

In other words, mapping a filter graph to a stack is trivial, just as going from a stack to a filter graph is also trivial – we can also go to an unambiguous infix representation (to avoid the 'educational' requirement we could simply enforce potentially redundant parenthesis in the output). For consistency, the document adopts a graph representation such that the top left operator is the one from which the application will use and all others will be pulled on demand from that operator: 

+
  sin
    x
  1

This is essentially the previous graph rotated 90 degree counter clockwise with the connectors removed - it is generated by a simple walk of the generated filter graph.

Note that this graph orientation is a purely arbitrary one – as arbitrary as, say, in-fix arithmetic. Since this document will contain a lot of graphs, the author considered it counter productive to pander to more socially acceptable conventions – such as drawing boxes and connectors between them. It's the laziness thing, right?