( 5 )
Previous Table Of Contents Next


Reverse Polish Notation

In the previous section I argued that RPN calculators were more consistent than conventional (usually called algebraic) calculators, since you could count on activity occurring whenever you pressed a key, and because all operands for all functions were handled identically: always taken off a stack. These are nice features, but they do not really explain why RPN calculators were built.

RPN was simpler for both the human operator and for the hardware (the machine). I have to use the past tense because the adoption of parentheses keys on algebraic calculators earned them the "simpler to operate" title. Furthermore, the microelectronics revolution that allows millions of transistors to be placed on a small chip of silicon meant that it was no longer necessary to employ the simplest circuit design. Consequently, algebraic calculators way outsell RPN calculators today.

To understand the parentheses issue, you must consider a math problem involving precedence, which is the order that operations must be performed to obtain the correct result. As an example, consider the problem of computing:

     2 * 3 + 4 * 5

Because multiplication has higher precedence than addition this problem should be performed as:

     ( 2 * 3 ) + ( 4 * 5 )

and hence the answer is 6 + 20 = 26. When confronted with this problem armed only with an antique algebraic calculator (that is, one that lacks parentheses keys), the operator is forced to employ the following keystroke sequence:


Observe that you need 12 keystrokes. On an RPN calculator we can solve this problem with fewer keystrokes by leaving the intermediate result of 2 * 3 on the stack while we compute the other intermediate result of 4 * 5. Study how this is accomplished with the following keystroke sequence:


Even though the above illustrations show that the operand stack initially held nothing but zeros, this same sequence of keystrokes will compute (2 * 3 ) + ( 4 * 5 ) regardless of the initial state of the stack. That is, we can put our new operands in the stack and operate upon them without any interference from the original stack contents.

Using the RPN calculator we need only 9 keystrokes to compute (2 * 3 ) + ( 4 * 5 ). Note that even with a modern algebraic calculator having parentheses keys, this problem still requires 12 keystrokes. But on more complicated examples the parenthesis keys do simplify the operator's job of expressing the problem to the calculator.

So why have I chosen an RPN calculator for use in my programming curriculum? Because of the prominence of the stack. Stacks are a vital component in all computers. They are the invention that allows an arbitrary section of a computer program to employ (call into) any other arbitrary section of the program. Every computer and calculator includes at least one stack and some computers (such as the Burroughs B5000 and the HP-300) were designed around an operand stack exactly like the one in our RPN calculator. Stacks are so ubiquitous that the RPN calculator actually has a second stack that we will encounter shortly.

The name stack was selected for this invention because it operates exactly the same as a stack of dishes: you can only add a new dish on the top and you can only take a dish from the top. The stack in the RPN calculator loads and empties from the bottom but the critical aspect is the last in, first out nature of the device.

Here's a cute thing you can do with the stack. Programmers (for reasons that will become clear when we next study the 8051 microprocessor) are always needing to compute the sequence of powers of 2; i.e., 2, 4, 8, 16, 32 ... An RPN calculator allows you to compute this infinite sequence using fewer keystrokes than any other calculator. In fact, a single keystroke is sufficient to produce each subsequent number in the sequence. To do this, first fully populate the stack with nothing but twos. You can do this via the keystrokes: 2, ENTER, 2, ENTER, 2, ENTER, 2. You are now ready to compute the sequence. Simply click on the Multiply button each time you want the next number in the sequence. Do you see why this works?

The name Reverse Polish Notation honors the Polish mathematician Jan Lukasiewicz who in the 1920's developed a formal logic system which allowed mathematical expressions to be specified unambiguously without the need for parentheses. There were two such approaches. In the first approach, known as Polish notation, the operator precedes both operands. Computer scientists today call this a prefix notation. In the second approach, known as reverse Polish notation, the operator follows both operands. Today, this is more commonly called postfix notation. The usual pencil and paper notation is called infix notation because the operator goes in between the operands.

It is possible to build a computer (or a computer programming language) that employs postfix notation:


or infix notation:


or prefix notation:


Of these 3 alternatives, postfix notation could be accomplished with the fewest storage locations and hence the fewest transistors. This one aspect was the deal breaker in electronic devices of the 1970s and hence Hewlett-Packard went with RPN notation for their line of hand calculators. But RPN isn't dead. Even today, most algebraic calculators convert an expression with parentheses into an equivalent RPN format before computing the result! And you might have heard of the PostScript language used with laser printers, it is another example of a postfix language.


Previous Table Of Contents Next