archive:programming:rpn
UNDERSTANDING REVERSE-POLISH NOTATION
For those of us using or considering a Hewlett-Packard scientific
calculator or computer, the question often arises, "What the heck
is Reverse-Polish Notation?"
The conventional mathematical notation we learned in high school
is known as "Algebraic Notation." In this notation, the
operators are placed either between or in front of the arguments.
Operators designate the operation to be performed ("+", "*",
"sin", etc.) and arguments are the values or variables upon which
they act ("1", "42.5", "pi", "x", etc.). A typical mathematical
expression might be:
sin[123 + 45 ln(27 - 6)]
The operators in this expression, from left to right, are "sin",
"+", "*" (implied between "45" and "ln"), "ln", and "-". By
their natures, "sin" and "ln" require one argument each while
"+", "*", and "-" require two each.
The arguments are not so easily determined. At first glance they
appear to be "123", "45", "27", and "6", but this is patently
false! The argument of "sin" is everything within the brackets,
or "123 + 45 ln(27 - 6)", those of "+" are "123" and "45 ln(27 -
6)", those of "*" are "45" and "ln(27 - 6)", that of "ln" is "27
- 6", and those of "-" are "27" and "6".
The whole expression may be thought of as a series of separate
operations:
sin[123 + 45 ln(27 - 6)] = sin(a) :: a = 123 + 45 ln(27 - 6)
123 + 45 ln(27 - 6) = 123 + b :: b = 45 ln(27 - 6)
45 ln(27 - 6) = 45 * c :: c = ln(27 - 6)
ln(27 - 6) = ln(d) :: d = 27 - 6
27 - 6
It is because of this that complex expressions are performed from
the inside out:
sin[123 + 45 ln(27 - 6)] = sin[123 + 45 ln(21)
sin[123 + 45 ln(21)] = sin(123 + 45 * 3.04452243772)
sin(123 + 45 * 3.04452243772) = sin(123 + 137.003509697)
sin(123 + 137.003509697) = sin(260.003509697)
sin(260.003539697) = 0.680672740775
In this manner, it can easily be seen that each operation is a
function of its argument or arguments, and an argument may itself
be a function of other arguments. Therefore, if we were to treat
the operations exactly as functions of arguments in the
traditional (x) and (y,x) formats, the expression "27 - 6"
would become -(27,6), where "-" is the operator "", "27" is the
argument "y", and "6" is the argument "x":
27 - 6 ÄÄ> -(27,6)
This is a two-argument function: in any two-argument function,
the second argument will always act against the first argument.
In this case, the second argument "6" will be subtracted from the
first argument "27".
The concept of treating all operators as functions is not as
strange as it first appears when you consider that a considerable
number of operators are already functions: ln(x) is (x) where
"" is "ln".
In the case of our example expression, the next function out is
ln(d), where "d" is itself the function -(27,6):
27 - 6 ÄÄ> -(27,6)
ln(27 - 6) ÄÄ> ln(-(27,6))
45 ln(27 - 6) ÄÄ> *(45,ln(-(27,6)))
123 + 45 ln(27 - 6) ÄÄ> +(123,*(45,ln(-(27,6))))
sin[123 + 45 ln(27 - 6)] ÄÄ> sin(+(123,*(45,ln(-(27,6)))))
The final function sin(+(123,*(45,ln(-(27,6))))) may at first
seem confusing, especially with all the parentheses, until one
remembers that it is the one-argument function sin(x). Once this
is realized, then everything within the parenthesis following
"sin" must be the one and only argument of sin(): the argument
of sin() must be +(123,*(45,ln(-(27,6)))).
In a similar manner, +(123,*(45,ln(-(27,6)))) is the two-argument
function +(y,x), where "y" is "123" and "x" is *(45,ln(-(27,6))).
A further clarification can be made if "+(y,x)" is thought of as
"the sum of y and x" (just as "ln(x)" is "the natural logarithm
of x"). This approach allows "sin(+(123,*(45,ln(-(27,6)))))" to
be read as "the sine of the sum of 123 and the product of 45 and
the natural logarithm of the difference of 27 and 6." This
phrase readily illustrates its clarity when empasized function by
function:
sin(+(123,*(45,ln(-(27,6)))))
The sine of sin(...)
the sum of sin(+(...))
123 and the product of sin(+(123,*(...)))
45 and the natural logarithm of sin(+(123,*(45,ln(...))))
the difference of sin(+(123,*(45,ln(-(...)))))
27 and 6. sin(+(123,*(45,ln(-(27,6)))))
Awkward as that may seem, it is much cleaner and more
straightforward than "sin[123+45ln(27-6)]," which is "the sine of
the quantity 123 plus 45 times the natural logarithm of the
quantity 27 minus 6."
What is even more important, it is unambiguous! If you heard
someone say "the quantity 123 plus 45 times the natural logarithm
of ...," does the speaker mean "(123+45)ln()" or
"(123+(45ln()))". By defining all operations as functions there
is no ambiguity, ever!
In algebra, a complex set of rules has been established as
regards order and priority of operations, and if these rules are
strictly followed there will be no ambiguity. Unfortunately, few
of the "algebraic" calculators or software packages on the market
follow these rules properly, and there is a total lack of
consistency in which rules are overlooked or changed.
What is needed with a calculator or computer is a mechanistic and
totally unambiguous method of operation. Treating all arguments
as functions provides just such a method and is known as Polish
Notation after its creator, the Polish logician Jan Lukasiewicz.
The complex function sin(+(123,*(45,ln(-(27,6))))) has one and
only one possible meaning, whether written in mathematical
symbology or spoken aloud.
Further research by the logicians at Hewlett-Packard provided a
slight variation on the theme. If instead of placing the
function ahead of its argument(s), it is placed behind, we get:
sin(+(123,*(45,ln(-(27,6)))))
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
sin( ) ÄÄ> ( )sin
+(123, ) ÄÄ> (123, )+
*(45, ) ÄÄ> (45, )*
ln( ) ÄÄ> ( )ln
-(27,6) ÄÄ> (27,6)-
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
((123,(45,((27,6)-)ln)*)+)sin
This method is known as Reverse Polish Notation, or RPN, in honor
of the original method. RPN, like Polish Notation, is
unambiguous: the order and only the order of arguments and
operators will determine the result. Since this is the case, the
parentheses and commas are irrelevant, and we may express our
function as:
((123,(45,((27,6)-)ln)*)+)sin ÄÄ> 123 45 27 6 - ln * + sin
This allows a simple and straightforward solution to calculator
or software mathematics: treat both the functions and their
arguments alike as "objects," and process them in a last-in,
first-out (LIFO) storage structure, a "stack."
When a function-object is entered onto the stack, it operates
upon the argument-object(s) already there to produce a result,
which replaces the argument-object(s). The stack adjusts
accordingly. This can be seen as:
object stack level x: y: z: t:
ÄÄÄÄÄÄ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÂÄÄÄÄÄÂÄÄÄÄÄ¿
123 ³ 123 ³ ³ ³ ³
45 ³ 45 ³ 123 ³ ³ ³
27 ³ 27 ³ 45 ³ 123 ³ ³
6 ³ 6 ³ 27 ³ 45 ³ 123 ³
- ³ -(27,6) ³ 45 ³ 123 ³ ³
ln ³ ln(-(27,6)) ³ 45 ³ 123 ³ ³
* ³ *(45,ln(-(27,6))) ³ 123 ³ ³ ³
+ ³ +(123,*(45,ln(-(27,6)))) ³ ³ ³ ³
sin ³ sin(+(123,*(45,ln(-(27,6))))) ³ ³ ³ ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÁÄÄÄÄÄÁÄÄÄÄÄÁÄÄÄÄÄÙ
The secret behind RPN's sophisticated yet simple power is in the
stack. In computer terms, a stack is an area in which pieces of
information may be stored on a last-in, first-out (LIFO) basis.
Think of the stack as a stack of plates: the last plate placed
on the stack will be the first plate used.
Most simple RPN calculators use a four-level stack, with the
levels labeled "x", "y", "z", and "t". Some newer, more
sophisticated calculators (such as the HP-28S and the HP-48SX)
and most software programs use an "infinite" stack: the number
of stack levels is limited only by available memory. The levels
in an infinite stack are usually numerical.
Entering a value will cause a stack lift: existing values will
be pushed up a level.
Entering a function will consume the arguments of the function.
If this consumption causes a "hole," the values above the hole
will be dropped to fill the hole.
Following through our example on an HP-48SX calculator:
ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
123 ³ 1: 123 ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
³ 2: 123 ³
45 ³ 1: 45 ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
³ 3: 123 ³
³ 2: 45 ³
27 ³ 1: 27 ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
³ 4: 123 ³
³ 3: 45 ³
³ 2: 27 ³
6 ³ 1: 6 ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
³ 3: 123 ³
³ 2: 45 ³
- ³ 1: 21 ³ -(27,6)
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
³ 3: 123 ³
³ 2: 45 ³
ln ³ 1: 3.04452243772 ³ ln(-(27,6))
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
³ 2: 123 ³
* ³ 1: 137.003509697 ³ *(45,ln(-(27,6)))
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
+ ³ 1: 260.003509697 ³ +(123,*(45,ln(-(27,6))))
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
sin ³ 1: .680672740775 ³ sin(+(123,*(45,ln(-(27,6)))))
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
/home/gen.uk/domains/wiki.gen.uk/public_html/data/pages/archive/programming/rpn.txt · Last modified: 1999/08/01 17:20 by 127.0.0.1