236 lines
12 KiB
Plaintext
236 lines
12 KiB
Plaintext
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 <20>(x) and <20>(y,x) formats, the expression "27 - 6"
|
||
would become -(27,6), where "-" is the operator "<22>", "27" is the
|
||
argument "y", and "6" is the argument "x":
|
||
|
||
27 - 6 <20><>> -(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 <20>(x) where
|
||
"<22>" 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 <20><>> -(27,6)
|
||
ln(27 - 6) <20><>> ln(-(27,6))
|
||
45 ln(27 - 6) <20><>> *(45,ln(-(27,6)))
|
||
123 + 45 ln(27 - 6) <20><>> +(123,*(45,ln(-(27,6))))
|
||
sin[123 + 45 ln(27 - 6)] <20><>> 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)))))
|
||
<20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
||
sin( ) <20><>> ( )sin
|
||
+(123, ) <20><>> (123, )+
|
||
*(45, ) <20><>> (45, )*
|
||
ln( ) <20><>> ( )ln
|
||
-(27,6) <20><>> (27,6)-
|
||
<20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
||
((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 <20><>> 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:
|
||
<20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD> <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ŀ
|
||
123 <20> 123 <20> <20> <20> <20>
|
||
45 <20> 45 <20> 123 <20> <20> <20>
|
||
27 <20> 27 <20> 45 <20> 123 <20> <20>
|
||
6 <20> 6 <20> 27 <20> 45 <20> 123 <20>
|
||
- <20> -(27,6) <20> 45 <20> 123 <20> <20>
|
||
ln <20> ln(-(27,6)) <20> 45 <20> 123 <20> <20>
|
||
* <20> *(45,ln(-(27,6))) <20> 123 <20> <20> <20>
|
||
+ <20> +(123,*(45,ln(-(27,6)))) <20> <20> <20> <20>
|
||
sin <20> sin(+(123,*(45,ln(-(27,6))))) <20> <20> <20> <20>
|
||
<20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
||
|
||
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:
|
||
|
||
<20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ŀ
|
||
123 <20> 1: 123 <20>
|
||
<20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
||
<20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ŀ
|
||
<20> 2: 123 <20>
|
||
45 <20> 1: 45 <20>
|
||
<20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
||
<20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ŀ
|
||
<20> 3: 123 <20>
|
||
<20> 2: 45 <20>
|
||
27 <20> 1: 27 <20>
|
||
<20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
||
<20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ŀ
|
||
<20> 4: 123 <20>
|
||
<20> 3: 45 <20>
|
||
<20> 2: 27 <20>
|
||
6 <20> 1: 6 <20>
|
||
<20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
||
<20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ŀ
|
||
<20> 3: 123 <20>
|
||
<20> 2: 45 <20>
|
||
- <20> 1: 21 <20> -(27,6)
|
||
<20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
||
<20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ŀ
|
||
<20> 3: 123 <20>
|
||
<20> 2: 45 <20>
|
||
ln <20> 1: 3.04452243772 <20> ln(-(27,6))
|
||
<20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
||
<20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ŀ
|
||
<20> 2: 123 <20>
|
||
* <20> 1: 137.003509697 <20> *(45,ln(-(27,6)))
|
||
<20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
||
<20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ŀ
|
||
+ <20> 1: 260.003509697 <20> +(123,*(45,ln(-(27,6))))
|
||
<20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
||
<20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ŀ
|
||
sin <20> 1: .680672740775 <20> sin(+(123,*(45,ln(-(27,6)))))
|
||
<20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
||
|