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?
20.10 Case Study: Evaluating Expressions
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