Java Reference
In-Depth Information
5.11
Recall that in a postfix expression, a binary operator follows its two operands. Here are a few
examples of infix expressions and their corresponding postfix forms:
Infix
Postfix
a
+
b
a
b
+
(
a
+
b
)
*
c
a
b
+
c
*
a
+
b
*
c
a
b
c
*
+
Notice that the order of the operands
a
,
b
, and
c
in an infix expression is the same in the corre-
sponding postfix expression. However, the order of the operators might change. This order depends
on the precedence of the operators and the existence of parentheses. As we mentioned, parentheses
do not appear in a postfix expression.
5.12
A pencil and paper scheme.
One way to determine where the operators should appear in a postfix
expression begins with a fully parenthesized infix expression. For example, we write the infix expres-
sion (
a
+
b
)
*
c
as ((
a
+
b
)
*
c
). By adding parentheses, we remove the expression's dependence on the
rules of operator precedence. Each operator is now associated with a pair of parentheses. We now
move each operator to the right so that it appears immediately before its associated close parenthesis
to get ((
a
b
+
)
c
*
). Finally, we remove the parentheses to obtain the postfix expression
a
b
+
c
*
.
This scheme should give you some understanding of the order of the operators in a postfix
expression. It also can be useful when checking the results of a conversion algorithm. However, the
algorithm that we will develop next is not based on this approach.
Question 4
Using the previous scheme, convert each of the following infix expressions to
postfix expressions:
a.
a
+
b
*
c
b.
a
*
b
/
(
c
-
d
)
c.
a
/
b
+
(
c
-
d
)
d.
a
/
b
+
c
-
d
5.13
The basics of a conversion algorithm.
To convert an infix expression to postfix form, we scan the
infix expression from left to right. When we encounter an operand, we place it at the end of the new
expression that we are creating. Recall that operands in an infix expression remain in the same
order in the corresponding postfix expression. When we encounter an operator, we must save it
until we determine where in the output expression it belongs. For example, to convert the infix
expression
a
+
b
, we append
a
to the initially empty output expression, save
+
, and append
b
to the
output expression. We now need to retrieve the
+
and put it at the end of the output expression to get
the postfix expression
a
b
+
. Retrieving the operator saved most recently is easy if we have saved it
in a stack.
In this example, we saved the operator until we processed its second operand. In general, we
hold the operator in a stack at least until we compare its precedence with that of the next operator.
For example, to convert the expression
a
+
b
*
c
, we append
a
to the output expression, push
+
onto
a stack, and then append
b
to the output. What we do now depends on the relative precedences of
the next operator,
*
, and the
+
at the top of the stack. Since
*
has a greater precedence than
+
,
b
is
not the addition's second operand. Instead, the addition waits for the result of the multiplication.
Thus, we push
*
onto the stack and append
c
to the output expression. Having reached the end of
the input expression, we now pop each operator from the stack and append it to the end of the out-
put expression, getting the postfix expression
a
b
c
*
+
. Figure 5-7 illustrates these steps. The stack
is shown horizontally; the leftmost element is at the bottom of the stack.
