Java Reference
In-Depth Information
FIGURE 5-7
Converting the infix expression
a
+
b
*
c
to postfix form
Next Character in
Infix Expression
Postfix Form
Operator Stack
(bottom to top)
a
+
b
*
c
a
a
a b
a b
a b c
a b c
*
a b c
* +
+
+
+ *
+ *
+
5.14
Successive operators with the same precedence.
What if two successive operators have the same
precedence? We need to distinguish between operators that have a left-to-right association—
namely
+
,
-
,
*
, and
/
—and exponentiation, which has a right-to-left association. For example, con-
sider the expression
a
-
b
+
c
. When we encounter the
+
, the stack will contain the operator
-
and
the incomplete postfix expression will be
ab
. The subtraction operator belongs to the operands
a
and
b
, so we pop the stack and append
-
to the end of the expression
ab
. Since the stack is empty,
we push the
+
onto the stack. We then append
c
to the result, and finally we pop the stack and
append the
+
. The result is
a b
-
c
+
. Figure 5-8a illustrates these steps.
Now consider the expression
a
^
b
^
c
. By the time we encounter the second exponentiation
operator, the stack contains
^
, and the result so far is
ab
. As before, the current operator has the
same precedence as the top entry of the stack. But since
a
^
b
^
c
means
a
^
(
b
^
c
), we must push
the second
^
onto the stack, as Figure 5-8b shows.
FIGURE 5-8
Converting an infix expression to postfix form:
(a)
a
-
b
+
c
; (b)
a
^
b
^
c
(a)
Next Character in
Infix Expression
Postfix Form
Operator Stack
(bottom to top)
a
-
b
+
a
a
a b
a b
-
a b
-
a b
-
c
a b
-
c
+
-
-
+
+
c
(b)
Next Character in
Infix Expression
Postfix Form
Operator Stack
(bottom to top)
a
^
b
^
c
a
a
a b
a b
a b c
a b c
^
a b c
^ ^
^
^
^ ^
^ ^
^
