CPSC170 Lab10

!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> CPSC170 Lab10

CPSC 170 Lab 10: Processing with Stacks

As usual, create a lab10 subdirectory for today's lab, open this document in Firefox, and start emacs.

Open a file called "Lab10Answers-XXX" where XXX are your initials. You will record some of your thoughts in this file over the course of the lab.

Implementing Stacks

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 file ArrayStack.java 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:

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. Why is this method private? (include in Answer file)
The pop and peek throw an EmptyStackException, this is implemented in EmptyStackException.java

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.

If you pop or peek at and empty stack - what happens? Explain precisely how the message arrives in your answers file.

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.
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:

create a copy of TestArrayStack.java (called TestLinearStack.java)
Edit the new file, chaning ArrayStack to LinearStack, where ever it occurrs (5 places - 2 are comments)
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.

Print copies of LinearStack and TestLinearStack to hand in.

Post-fix Notation

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

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 can't do.
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? (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? Make it happen and fix this mess.

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 /.

Here is an outline of the general algorithm:

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 to postfix
if the token is an operator, process the operator (described below)

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

3 + 7 * 5
3 * 5 + 7
3 + 5 * 2 - 4

InfixToPostfix.java

Once your code works with Infix expressions containing the operators +, -, * and /, we want to modify the program to also work with parentheses. This is a realtively easy fix, involving two changes

Parentheses need to be recognized operators with precedence 1.
Modify the processOperator Method as follows

Check to see operator is not an opening parethesis '('

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 hand in.

HAND IN:

Turn in hardcopies of your code

Tar your directory and email to me with cpsc170 lab10 in the Subject line.