In school, while learning basic arithmetic, students are also taught precedence rules for the various arithmetic operators. This is often done using a mnemonic such as "My Dear Aunt Sally" (denoting the order as Multiplication, Division, Addition, and Subtraction). Therefore, given an expression 2 + 3 x 4 - 1, we know that the multiplication should be evaluated first, followed by the addition and finally the subtraction--the answer thus is 12 + 2 - 1, or 13.
This order of operator precedence is also important in programming, because expressions should be evaluated by the compiler in the same way that the programmer intended them to be. This happens only when the programmer who writes the code, and the compiler writer who determines how program statements are translated into machine code, have the same notation in mind. In most programming languages in use today, the notation in use is as described above, and both compiler writers and programmers define their statements accordingly. However, in some early electronic calculators, the notation was not fixed or else was hard-wired incorrectly into the device, hence for example the expression given above would evaluate to 19.
In many cases, it is desirable to remove all ambiguity by using brackets. If the programmer specified the statement as (2 + (3 x 4)) - 1, even the most dense compiler would be rightly expected to interpret his intentions correctly.
In the early days of electronic calculators, these precedence rules proved to be very difficult to implement in the hardware of the time. Calculator designers, especially at Hewlett Packard, came to realize that another notation could be used. The Polish notation, named after its creator Polish mathematician Jan Lukasiewicz (1878-1956), was created in the 1920s for use in evaluating expressions in symbolic logic. A variant of this notation, called the Reverse Polish Notation, was what the engineers at Hewlett-Packard decided to use.
Reverse Polish Notation is a way of expressing arithmetic expressions fully and unambiguously while avoiding the use of brackets to define operator precedence. In ordinary notation, one might write an expression as (1 + 4) x (8 - 5)--the brackets just specify that first we have to add 1 to 4, then subtract 5 from 8, and lastly multiply the two results together.
In the Reverse Polish Notation, numbers and operators are listed one after the other, and an operator always acts on the closest numbers on the list. The whole situation can be thought of in terms of stacks--the most recent number goes on top of the stack; the operator takes the appropriate number of arguments from the top of the stack, and replaces them by the result of its operation on them. The expression has been evaluated completely once the stack contains just a single number and no arithmetic operator.
In this notation, the above expression would be: 1 <enter> 4 <enter> + 8 <enter> 5 - x (we need the <enter> key to separate the numbers, else the calculator would not know that 1 and 4 were separate numbers rather than the two digits of 14).
Read from left to right, this is interpreted as follows:
Push 1 onto the stack.
Push 4 onto the stack. The stack now contains (1, 4).
Apply the + operation--take the top two numbers off the stack, add them together, and put the result back on the stack. The stack now contains just the number 5.
Push 8 onto the stack.
Push 5 onto the stack. It now contains (5, 8, 5).
Apply the - operation--take the top two numbers off the stack, subtract the top one from the one below, and put the result back on the stack. The stack now contains (3, 5).
Apply the x operation--take the top two numbers off the stack, multiply them together, and put the result back on the stack. The stack now contains just the number 15--the answer.
In the Polish notation, the one originally used by Lukasiewicz, the operators preceded their arguments, so that the expression above would be written as x + 1 <enter> 4 <enter> - 8 <enter> 5 <enter>. The "reversed" form, which is similar to German (all verbs at the end of the sentence!) has however been found more convenient in computation.
Calculators using conventional algebraic input semantics also work using the Reverse Polish Notation, but they convert the input expression into that form internally before evaluating it. Early calculators by Hewlett-Packard and other manufacturers were unable to do this, so they relied on the human user to correctly supply the expression in RPN format. This made for some effort on the part of the users initially, but most people got used to it when they needed to. Some hardware manufacturers, including Hewlett-Packard, still manufacture RPN devices for those who are used to the syntax. Some modern calculators also offer the choice between the Reverse Polish Notation and the conventional one, as a user-configurable option.
This is the complete article, containing 807 words
(approx. 3 pages at 300 words per page).
