Java Reference
In-Depth Information
Question 6
Using the previous algorithm, represent each of the following infix expres-
sions as a postfix expression:
a.
(
a
+
b
)
/
(
c
-
d
)
b.
a
/
(
b
-
c
)
*
d
c.
a
-
(
b
/
(
c
-
d
)
*
e
+
f
)
^
g
d.
(
a
-
b
*
c
)
/
(
d
*
e
^
f
*
g
+
h
)
Evaluate a postfix expression that uses the operators
+
,
-
,
*
,
/
, and
^
to indicate addition, sub-
traction, multiplication, division, and exponentiation.
5.17
Evaluating a postfix expression requires no rules of operator precedence, since the order of its oper-
ators and operands dictates the order of the operations. Additionally, a postfix expression contains
no parentheses to complicate the evaluation.
As we scan the postfix expression, we must save operands until we find the operators that
apply to them. For example, to evaluate the postfix expression
a
b
/
, we locate the variables
a
and
b
and save their values.
2
When we identify the operator
/
, its second operand is the most
recently saved value—that is,
b
's value. The value saved before that—
a
's value—is the opera-
tor's first operand. Storing values in a stack enables us to access the necessary operands for an
operator. Figure 5-10 traces the evaluation of
a
b
/
when
a
is 2 and
b
is 4. The result of 0 assumes
integer division.
VideoNote
Using the ADT stack
FIGURE 5-10
The stack during the evaluation of the postfix expression
a
b
/
when
a
is 2 and
b
is 4
/
/
4
a
b
/
/
4
2 / 4
2 / 4
4
4
4
2
2
2
2
2
2
0
Now consider the postfix expression
a
b
+
c
/
, where
a
is 2,
b
is 4, and
c
is 3. The expression
corresponds to the infix expression (
a
+
b
)
/
c
, so its value should be 2. After finding the variable
a
,
we push its value 2 onto a stack. Likewise, we push
b
's value 4 onto the stack. The
+
operator is
next, so we pop two values from the stack, add them, and push their sum 6 onto the stack. Notice
that this sum will be the first operand of the
/
operator. The variable
c
is next in the postfix
expression, so we push its value 3 onto the stack. Finally, we encounter the operator
/
, so we pop
two values from the stack and form their quotient, 6
/
3. We push this result onto the stack. We are
2.
Finding the value of a variable is not an easy task, but we will not explore this detail in this topic.
