Hardware Reference
In-Depth Information
1. The car at the switch heads toward Texas.
2. The most recent car on the Texas line turns and goes to California.
3. Both the car at the switch and the most recent car on the Texas line
are diverted and disappear (i.e., both are deleted).
4. Stop. The symbols now in California represent the reverse Polish
notation formula when read from left to right.
5. Stop. An error has occurred. The original formula was not correctly
balanced.
Car at the switch
⊥
+-x/ ()
⊥
+
-
x
/
(
4
1
1
1
1
1
5
2
2
2
1
1
1
2
2
2
2
1
1
1
2
2
2
2
2
2
1
2
2
2
2
2
2
1
2
5
1
1
1
1
1
3
Figure 5-21.
Decision table used by the infix-to-reverse Polish notation algorithm
After each action is taken, a new comparison is made between the car currently
at the switch, which may be the same car as in the previous comparison or may be
the next car, and the car that is now the last one on the Texas line. The process
continues until step 4 is reached. Notice that the Texas line is being used as a
stack, with routing a car to Texas being a push operation, and turning a car already
on the Texas line around and sending it to California being a pop operation.
Infix
Reverse Polish notation
A+B
×
C
ABC
×
+
A
×
B+C
AB
×
C+
A
×
B+C
×
D
A B
×
CD
×
+
(A+B)/(C
−
D)
AB+CD
−
/
A
×
B/C
AB
×
C/
((A+B)
×
C + D)/(E+F+G)
AB+C
×
D+EF+G+/
Figure 5-22.
Some examples of infix expressions and their reverse Polish nota-
tion equivalents.
The order of the variables is the same in infix and in reverse Polish notation.
The order of the operators, however, is not always the same. Operators appear in
