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>
|
|||
|
|
|