RPN meaning: Reverse Polish Notation


Brief explanation of RPN
------------------------
Written by: A G Suárez. (algesuar)

----------------------------------------------------------------------------
EXCUSE MY ENGLISH. The first version of this document was written in spanish.
If you find english errors please e-mail me.
---------------------------------------------------------------------------- 

The HP41 calculator as all Hewlett Packard calculators, has a different
form to do operations.

First of all, the equal key does not exist.

To sum 4 + 5 is necessary to key in:

[4] [ENTER] [5] [+]

As you can see, the add key is pushed at the end. Also there is a key
Enter that must be pressed to split the two numbers to add.

If we want to do the following operation: (4+5)*2

on the HP41 the keys to press are:

[4] [ENTER] [5] [+] [2] [*]  

On a normal calculator we would have to digit:

[4] [+] [5] [=] [*] [2] [=]  

In the first case we pressed 6 keys, on the normal calculator
were 7 keys. We saved: 1 key.

To do the following operation:

3+6
----
11+7

On a normal calculator we enter:

[1] [1] [+] [7] [=] [M+] [3] [+] [6] [=] [/] [MR] [=] : Total, 13 keys

being [M+] save a memory and [MR] recall a memory.

On the Hewlett Packard:

[3] [ENTER] [6] [+] [1] [1] [ENTER] [7] [+] [/] : Total, 10 keys

We saved: 3 keys.


Although, at the beginning, it may seem a bit strange the manner to execute
operations, when time pass it is found that to operate in this form one
calculator is very advantageous: We save many keys on big calculus .

Internally exist a set of 4 registers named the "Stack" (the pile)(the heap).
These registers allow to do this type of operations.

The registers are named X, Y, Z, T . The register X allways is shown on the
display.

When the key [ENTER] is pressed internaly the contents of register X
is copied to register Y. When one operation is executed as, for example,
[+], registers X (display) and Y are sumed and the result is placed on the
display (Register X).

We could think that the 4 registers are on a pile with 4 levels where
the inferior (less) level is X, the second level is Y, Z the third level and T the 
fourth level.


------------------ | Register T | Level 4 ------------------ | Register Z | Level 3 ------------------ | Register Y | Level 2 ------------------ | Register X | Level 1 (shown on the calculator display) ------------------
The [ENTER] key copies the content of register X to Y as we said before, but also occurs that the value of Y is copied or "goes up" to register "Z" and the value of Z goes up to register T. The previous value of T is lost because no exist room to copy the value. When an operation is executed, for example [*] the content of all registers go down on the "stack" in such form that T is copied on Z, Z on Y and Y over X. In this case Y and X are multiplied leaving the result in X. This secuence of operations follows some rules known as RPN that means "Reverse Polish Notation" in honor (honour) to a polish matematician who invented it. In polish notation to sum 4 and 5 we put + 4 5 with the operator preceding the numbers to operate. In the reverse polish notation is written: 4 5 + To indicate to the calculator that we are not writing forty five, and only 4 and 5 , [ENTER] is used as separator. When we press [+] the operation is ended. RPN examples: 1.Execute (4+6) * (3+2)
[4] [ENTER] [6] [+] [3] [ENTER] [2] [+] [*]
2. Calculate 9 / (2+1)
[9] [ENTER] [2] [ENTER] [1] [+] [/]
Also, using the function 1/x that calculates the inverse of a number we could answer this example in the form: [2] [ENTER] [1] [+] [1/x] [9] [*] 3. Calculate 3+5 6-2 --- + --- 2 3+1
[3] [ENTER] [5] [+] [2] [/] [6] [ENTER] [2] [-] [3] [ENTER] [1] [+] [/] [+]
Also it is possible: [2] [1/x] [3] [ENTER] [5] [+] [*] [3] [ENTER] [1] [+] [1/X] [6] [ENTER] [2] [-] [*] [+] 4. Sum 1+2+3+4. All the following possibilities are solutions:
[1] [ENTER] [2] [+] [3] [+] [4] [+] [1] [ENTER] [2] [ENTER] [3] [ENTER] [4] [+] [+] [+] [1] [ENTER] [2] [+] [3] [ENTER] [4] [+] [+] [1] [ENTER] [2] [ENTER] [3] [+] [+] [4] [+]
In all previous sequences the "stack" saves dinamically the intermediate values. The function [Y^X] raises the value in the Y register to the exponent found in the x register (display). To calculate 4^2 = 16 we proceed in the following way: [4] [ENTER] [2] [Y^X] This means that first "go up" (move up) the "4" to register Y using "Enter", later we enter (write) a 2 on the display and then we press the function key. Example 5. Calculate 3* 2^4 + 5
[3] [ENTER] [2] [ENTER] [4] [Y^X] [*] [5] [+]
Also: [2] [ENTER] [4] [Y^X] [3] [*] [5] [+] Entering (putting) the 5 at the beginning: [5] [ENTER] [2] [ENTER] [4] [Y^X] [3] [*] [+] Placing (inserting) the 5 and the 3 first: [5] [ENTER] [3] [ENTER] [2] [ENTER] [4] [Y^X] [*] [+] Example 6: Analize how many levels of the "stack" requires each one of the forms (ways) to sum 1+2+3+4 of example 4.
[1] [ENTER] [2] [+] [3] [+] [4] [+] requires two levels X and Y [1] [ENTER] [2] [ENTER] [3] [ENTER] [4] [+] [+] [+] requires 4 levels X,Y,Z,T [1] [ENTER] [2] [+] [3] [ENTER] [4] [+] [+] requires 3 levels X,Y,Z [1] [ENTER] [2] [ENTER] [3] [+] [+] [4] [+] requires 3 levels X,Y,Z
To answer this example we remember that each [ENTER] push the register X into Y but also push the remaining registers Z to T and Y to Z A single [ENTER] requires two storage registers, two [ENTER] requires 3 registers of storage and three [ENTER], 4 storage registers. The limits of the first generation of Hewlett Packard calculators are 4 registers, i.e., 4 stack levels, due to this we can use only [ENTER] 3 consecutive times. If we use [ENTER] 4 or more times we lost the first numbers. (the first data) Example 7: In the following secuence what data is lost:
[1] [ENTER] [2] [ENTER] [3] [ENTER] [4] [ENTER] [5]
The number 1 is lost because the stack limit is only 4 levels and we are climbing this number , the 1, to the fifth level , and that level does not exist. In this example, next to those operations: the number 1 is lost, the number 2 is placed on the fourth stack level, i.e. on T register, the number 3 is placed on third level: Z register, the number 4 is positioned on the second level: Y Register. At last, the 5 leaves on the first level (Register X), i.e. the number 5 is placed on the calculator display. In summary, whatever data to climb over register T, (fourth level), is scrapped by the calculator because there is not room to save it. The operations that require 2 values as [+] [-] [*] [/] [Y^X] take two values from registers X and Y leaving the result on register X (Display) Additionally go down the stack, i.e., the Z register goes down to Y and the T register goes down to Z. What is contained (exist) on T register after this goes down to Z?: The same value of T, i.e. , the T register , with each operation is copied downwards without experimenting changes itself. This behavior serves us to put a constant. For example, we want that each time we press the [+] key, add 3 to the display value. The form (the way) to do is: [3] [ENTER] [ENTER] [ENTER] Next, let`s type for example a [5] and later [+] the display shows 8 [+] the display shows 11 [+] the display shows 14 and so on... Example 8: Put the calculator in such form (such status) that each time the [*] key is pressed occurs one multiplication by 2.
[2] [ENTER] [ENTER] [ENTER]
The calculator is ready with the desired constant. Now let`s type for example 10 and later: [*] the display shows 20 [*] the display shows 40 [*] the display shows 80 [*] the display shows 160 and so on. If the calculator stack is filled with a constant we can also mix operators. Example 9:
[2] [ENTER] [ENTER] [ENTER]
"We fill" the stack with the constant 2. Now: [2] [*] [*] [*] [*] produce 32 [x<>y][/][x<>y][/] and we obtain 8, [+][*] and 20 is obtained, [-][*] and we reach a -36, [x<>y][/][-] and we have obtained 20 . Note: [x<>y] allows to interchange (swap) the registers X and Y. Other examples of [x<>y]: It is the same: [8][ENTER][2][/] Result: 4 [2][ENTER][8][X<>Y][/] Result: 4 Remember that [/] is not a conmutative operation. [2][ENTER][8][/] Result: 0.25 For that it is necessary to use [X<>Y] to place the numbers [8] and [2] in correct form (secuence) before to execute the operation. Example 10: Solve 4+5 using [x<>y] --- 2+1
[2][ENTER][1][+][4][ENTER][5][+][X<>Y][/]
Other possibilities are:
[4][ENTER][5][+][2][ENTER][1][+][/] [4][ENTER][5][ENTER][2][ENTER][1][+][+][/] [2][ENTER][1][+][1/X][4][ENTER][5][+][*] [2][ENTER][1][ENTER][4][ENTER][5][+][+][X<>Y][/]