Java Reference
In-Depth Information
20.30
How do you create a priority queue for integers? By default, how are elements
ordered in a priority queue? Is the element with the least value assigned the highest
priority in a priority queue?
20.31
How do you create a priority queue that reverses the natural order of the elements?
Stacks can be used to evaluate expressions.
Key
Point
Stacks and queues have many applications. This section gives an application that uses stacks
to evaluate expressions. You can enter an arithmetic expression from Google to evaluate the
expression, as shown in FigureĀ 20.15.
F
IGURE
20.15
You can evaluate an arithmetic expression using a Google search engine.
How does Google evaluate an expression? This section presents a program that evaluates a
compound expression
with multiple operators and parentheses (e.g.,
(15 + 2) * 34 - 2
).
For simplicity, assume that the operands are integers and the operators are of four types:
+
,
-
,
*
, and
/
.
The problem can be solved using two stacks, named
operandStack
and
operatorStack
,
for storing operands and operators, respectively. Operands and operators are pushed into
the stacks before they are processed. When an
operator is processed
, it is popped from
operatorStack
and applied to the first two operands from
operandStack
(the two oper-
ands are popped from
operandStack
). The resultant value is pushed back to
operandStack
.
The algorithm proceeds in two phases:
compound expression
process an operator
Phase 1: Scanning the expression
The program scans the expression from left to right to extract operands, operators, and the
parentheses.
1.1.
If the extracted item is an operand, push it to
operandStack
.
1.2. If the extracted item is a
+
or
-
operator, process all the operators at the top of
operatorStack
and push the extracted operator to
operatorStack
.
1.3. If the extracted item is a
*
or
/
operator, process the
*
or
/
operators at the top of
operatorStack
and push the extracted operator to
operatorStack
.
Search WWH ::
Custom Search