Java Reference
In-Depth Information
12.
Are the trees in
Figure 14
binary search trees?
R
ANDOM
F
ACT
16.1: Reverse Polish Notation
In the 1920s, the Polish mathematician Jan Ğukasiewicz realized that it is possible
to dispense with parentheses in arithmetic expressions, provided that you write the
operators before their arguments. For example,
Standard Notation
ÿukasiewicz Notation
3 + 4
+ 3 4
3 + 4 * 5
+ 3 * 4 5
3 * (4 + 5)
* 3 + 4 5
(3 + 4) * 5
* + 3 4 5
3 + 4 + 5
+ + 3 4 5
The Ğukasiewicz notation might look strange to you, but that is just an accident of
history. Had earlier mathematicians realized its advantages, schoolchildren today
would not learn an inferior notation with arbitrary precedence rules and
parentheses.
Of course, an entrenched notation is not easily displaced, even when it has distinct
disadvantages, and Ğukasiewicz's discovery did not cause much of a stir for about
50 years.
However, in 1972, Hewlett-Packard introduced the HP 35 calculator that used
reverse Polish notation or RPN. RPN is simply Ğukasiewicz's notation in reverse,
with the operators after their arguments. For example, to compute
3 + 4 * 5
,
you enter
3 4 5 * +
. RPN calculators have no keys labeled with parentheses or
an equals symbol. There is just a key labeled ENTE
R to push a number onto a
stack. For that reason, Hewlett-Packard's marketing
department used to refer to
their product as Ȓthe calculators that have no equalȓ. Indeed, the Hewlett-Packard
calculators were a great advance over competing models that were unable to
handle algebraic notation, leaving users with no other choice but to write
intermediate results on paper.
734
735
