Hardware Reference
In-Depth Information
c
) because multiplication
has been arbitrarily defined to have precedence over addition. But does left shift
have precedence over Boolean
AND
? Who knows? Reverse Polish notation elimi-
nates this nuisance.
Several algorithms for converting infix formulas into reverse Polish notation
exist. The one given below is an adaptation of an idea due to E. W. Dijkstra. As-
sume that a formula is composed of the following symbols: variables, the dyadic
(two-operand) operators +
know that
a
×
b
+
c
means (
a
×
b
)
+
c
and not
a
×
(
b
+
* /, and left and right parentheses. To mark the ends
of a formula, we will insert the symbol
−
after the last symbol and before the first
symbol.
A
x
(
B
+
C
)
⊥
California
New York
Switch
Texas
⊥
Figure 5-20.
Each railroad car represents one symbol in the formula to be con-
verted from infix to reverse Polish notation.
Figure 5-20 shows a railroad track from New York to California, with a spur in
the middle that heads off in the direction of Texas. Think of the New York to Cali-
fornia line as the main line with the branch down to Texas as a siding for tempo-
rary storage. The names and directions are not important. What matters is the dis-
tinction between the main line and the alternative place for temporarily storing
things. Each symbol in the formula is represented by one railroad car. The train
moves westward (to the left). When each car arrives at the switch, it must stop just
before it and ask if it should go to California directly or take a side trip to Texas.
Cars containing variables always go directly to California and never to Texas. Cars
containing all other symbols must inquire about the contents of the nearest car on
the Texas line before entering the switch.
The table of Fig. 5-21 shows what happens, depending on the contents of the
nearest car on the Texas line and the car poised at the switch. The first
always
goes to Texas. The numbers refer to the following situations:
