!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

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

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

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

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

Post-fix Notation

  1. 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
     
  2. 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:
  3. The precendence of the operators is determined as follows  +, -  have precendence 2,   *, / have precendence 3.  

    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

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

    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.


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

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