LISTS, STACKS, QUEUES, AND PRIORITY QUEUES - Introduction to Java Programming: Comprehensive Version - page 790

You can use the GenericStack class provided by the topic or the java.util.Stack
class defined in the Java API for creating stacks. This example uses the java.util.Stack
class. The program will work if it is replaced by GenericStack .
The program takes an expression as a command-line argument in one string.
The evaluateExpression method creates two stacks, operandStack and
operatorStack (lines 23, 26), and extracts operands, operators, and parentheses delimited
by space (lines 29-32). The insertBlanks method is used to ensure that operands, opera-
tors, and parentheses are separated by at least one blank (line 29).
The program scans each token in the for loop (lines 35-77). If a token is empty, skip it
(line 37). If a token is an operand, push it to operandStack (line 75). If a token is a + or
- operator (line 38), process all the operators from the top of operatorStack , if any (lines
40-46), and push the newly scanned operator into the stack (line 49). If a token is a * or /
operator (line 51), process all the * and / operators from the top of operatorStack , if any
(lines 53-57), and push the newly scanned operator to the stack (line 60). If a token is a (
symbol (line 62), push it into operatorStack . If a token is a ) symbol (line 65), process all
the operators from the top of operatorStack until seeing the ) symbol (lines 67-69) and
pop the ) symbol from the stack.
After all tokens are considered, the program processes the remaining operators in
operatorStack (lines 80-82).
The processAnOperator method (lines 90-103) processes an operator. The method pops
the operator from operatorStack (line 92) and pops two operands from operandStack
(lines 93-94). Depending on the operator, the method performs an operation and pushes the
result of the operation back to operandStack (lines 96, 98, 100, 102).

20.32

✓ ✓

Can the EvaluateExpression program evaluate the following expressions "1+2" ,
"1 + 2" , "(1) + 2" , "((1)) + 2" , and "(1 + 2)" ?

Check

Point

20.33

Show the change of the contents in the stacks when evaluating "3 + (4 + 5) *
(3 + 5) + 4 * 5" using the EvaluateExpression program.

20.34

If you enter an expression “4 + 5 5 5” , the program will display 10. How do you
fix this problem?

K EY T ERMS

collection 762
comparator 772
convenience abstract class

linked list 769

list 762
priority queue 762 783

data structure 762 queue 762

C HAPTER S UMMARY
1.

The Java Collections Framework supports sets , lists , queues , and maps . They are defined
in the interfaces Set , List , Queue , and Map .

2.

A list stores an ordered collection of elements.

3.

All the concrete classes except PriorityQueue in the Java Collections Framework
implement the Cloneable and Serializable interfaces. Thus, their instances can be
cloned and serialized.