CPSC 170 Lab 10: Processing with Stacks
As usual, create a lab1 subdirectory for today's lab, open
document in Firefox, and start
Create a textfile called "Lab10Answers-XXX" where XXX are your
initials. You will record some of your thoughts in this
file over the course of the lab.
- The file StackADT.java provides the
interface for the stack abstract data type. In class, we have
been discussing two data structures that can be used to implement this
useful data type -arrays and the linked structure. The
provides a working implementation of stack using arrays. Look
through the code to make sure that you understand how it is
functioning. Some things to observe:
The file TestArrayStack.java
contains code to use an ArrayStack. Download this code (and
the other three files) compile and run it. Use this code to
confirm your understand of how a stack operates.
- All the methods defined in StackADT (push, pop,
peek, isEmpty and size) are defined -understand what each is doing.
- There is also an additional method, expandCapacity.
- The pop and peek throw an EmptyStackException, this is
implemented in EmptyStackException.java
The file LinkedStack.java
provides a partial implementation of a stack using LinearNodes (the same structure we used
for lists and sets). Complete the implementation.
- If you pop or peek at and empty stack - what happens?
Explain precisely how the
message arrives in your answers file.
When you think that you have a working LinearStack, you want to
create a test file to verify that it is working correctly. In
fact, you already have one (well most of one). At the
interface level, the functionality of the ArrayStack is identical to
the LinearStack - all of the public methods are the same (as defined in
StackADT). To test your LinearStack, you can:
Print copies of LinearStack and TestLinearStack to hand
- create a copy of TestArrayStack.java (called
- Edit the new file, chaning ArrayStack to LinearStack, where
ever it occurrs
- Note: the only way that this program knows whether our
stack is implemented with an Array or a LinearNodes is by the way that
we named the classes. - there are no references to .next or [i] or
anything that reveals the data structure used to implement the
stack. The programmer who is using your class doesn't
need to know these details!
- Verify that your Linear Stack does, in fact, behave the same
way as the Array Stack.
- The file Postfix.java contains
a program that allows you to enter a post-fix expression and find the
answer. This is accomplished using the PostfixEvaluator class, which reads
the expression into a stack using the algorithm described in
class. Look at the code to verify that you understand the
operations that are taking place in this class
The idea of Postfix notation is nice because it means that we
don't need to worry about precedence. But how do we convert
Infix expressions to Postfix expressions? In this next
step, we will write a conversion routine. Conveniently
enough, the algorithm also uses a stack! We will start
working with expressions that do not contain parentheses - only the
operators +, - * and /.
- One thing that you might not be familiar with is a
"StringTokenizer". This behaves similar to a Scanner or an
Iterator; it subdivides the string up into "tokens" that are
delimited by some character (the default is a space). Once
divided up, the programmer can ask if the string "hasMoreTokens" and
can ask to receive the "nextToken". The programmer also has the
ability to return "countTokens" - something that Scanners and Iterators
- Another curious thing about this code is the stack that is
being used. Is it an array or a linked
structure? Where did this mysterious stack data type
come from? Make a note of the import statements at the top
of the code. Could it be that there is an implementation of
a stack in Java.util? Check the JavaDocs
to find out (try to find "Stack" in the "All classes"
pane. Does Java's stack follow the same interface
that our stack does? Does it have an iterator?
(include in Answer file)
- Make a note of what is happening when we pop the
stack. Hmmm.... this is weird. You are
witnessing a "hack". Something klugy done to make the
code work, but it is needed because we are doing something else not
quite right. Here was the programmer's
thinking: Generally, pop returns an object, but
I need an int. There is not a good way to go directly from
an object to an integer, but I can go from a String to an
integer. hmmm.. I can make the compiler convert the
object to a string by concatinating a string to it ( "" in the
example). So we convert the object to a string and
then pass the string to the Integer object constructor, which is cast
back to an int at the assignment statement. Whew - that was
muddled and convoluted. We can do better, by realizing that
that we can make Pop return an integer instead of an object. How
do we do that? (study the javaDocs to learn about
what the stack really stores and fix this mess.
Here is an outline
of the general algorithm:
The precendence of the operators is determined as follows +,
- have precendence 2, *, / have precendence
- Create an empty String called postfix
- Create an empty stack to hold operators (not operands!)
- While there are tokens in the infix string
- Get the next token
- if the token is an operand, append the token
- if the token is an operator, process the operator
- Pop remaining operators and add them to postfix
- To Process the operator: (treat this as a separate method)
- while the stack is not empty and precedence of this
operator is less than precedence of the top of operator stack
- pop top off stack and append to postfix
- push the new operator
The logic behind this algorithm may not be readily
apparent. Try tracing a few examples by hand first to
get a sense of how the algorithm functions. Here are some
that may be worth trying
Implement the algorithm decribed above. A framework for your code
can be found in the file InfixToPostfix.java
Test your evaluation by modifying Postfix.java so that the user first
enters an Infix expresss, which is converted to a Postfix expression
and then evaluated.
- 3 + 7 * 5
- 3 * 5 + 7
- 3 + 5 * 2 - 4
Once your code works with Infix expressions containing the
-, * and /, we want to modify the program to also work with
parentheses. This is a realtively easy fix, involving two
- Parentheses need to be recognized operators with
- Modify the processOperator Method as follows
- Check to see operator is not an opening
while (precedence(op) <= precedence(top() and
top is not '('
pop the top and append it to the postfix
expression (if it isn't a '(' )
- if the operator is not a closing paren ‘)’ push
it onto the stack.
Again, tinker with this algorithm on paper to make sure that you
understand how it is functioning. Once you are convinced
that this will work, update your code to reflect this new approach.
Print copies of Postfix, PostFixEvaluator and InfixToPrefixto
Turn in stapled hardcopies of your code
Tar your directory and email to me with cpsc170 lab10
the Subject line.