The TAO of Java

Laboratory: Stacks

Summary: In this laboratory, you will have an opportunity to ground your understanding of stacks, particularly of the array-based implementation of stacks.

Contents:

• Exercises
  • Exercise 0: Preparation
  • Exercise 1: Building a DynamicArrayBasedStack
  • Exercise 2: Basic Testing
  • Exercise 4: Testing peek
  • Exercise 5: Matching Parens
  • Exercise 6: Matching Multiple Symbols
• For Those With Extra Time
  • Extra 1: Matching Parens, Revisited
  • Extra 2: Displaying Matching Parens

Required Code Files:

• LinearStructure.java
• LinearTesterHelper.java
• Stack.java
• ArrayBasedStack.java
• TestArrayBasedStack.java

Exercises

Exercise 0: Preparation

In this laboratory, you will use a package entitled username.linear.

a. In a terminal window, type

/home/rebelsky/bin/tao linear

You should see messages about files being copied to a temporary directory.

b. Start Eclipse.

c. In Eclipse, build a project named Temp from /home/username/CSC152/Temp.

d. In the Temp project, you should see a package named username.linear. Drag that package to your Code project.

e. Delete the Temp project.

You can now work with the new package.

Exercise 1: Building a DynamicArrayBasedStack

One of the files that was downloaded with the package linear is called ArrayBasedStack, and as you might expect, it implements a Stack based on an array of Objects. However, this term instead of using the given ArrayBasedStack, you will implement your own Stack based on the DynamicArray class that you wrote in the previous lab.

Write a class that begins as follows:

import username.DynArray.DynamicArray;

public class DynamicArrayBasedStack<T>
  implements Stack<T>
{
  // +--------+------------------------------------------------------------
  // | Fields |
  // +--------+

  /** The dynamic array that stores the values. */
  DynamicArray<T> contents;

  /** The place in which the next value goes. (This is also the number of items currently in the stack.) */
  int top;

  // +-------------+-------------------------------------------------------
  // | Construtors |
  // +-------------+
 
  ...
}

Your class should include a constructor that generates an empty stack, and all of the methods in the Stack interface (which is in the package linear as Stack.java). Note that the reading on stacks includes most of the code that you will need to do this.

One method that is not specifically addressed in the reading is peek. This method should return the value of the element that was added to the stack most recently, but it should not remove that item or reduce the size of the stack.

Methods get and peek should throw exceptions if the stack is empty when they are called. A "java.util.EmptyStackException" would be good choice for this. (Note that since this is a "run-time" exception, you do not need to include a "throws" clause in the method header, and indeed you will make your life easier if you don't.)

Exercise 2: Basic Testing

Read through LinearTesterHelper.java.

a. Sketch the output you expect to receive if you create a LinearTesterHelper using a stack as a parameter and then execute the runStandardTests method in that class.

b. Look at TestArrayBasedStack to see that it does, in fact, build a LinearTesterHelper and ask it to execute the same series of operations.

c. Make one small modification to TestArrayBasedStack such that it generates a new DynamicArrayBasedStack to test. (It currently generates an ArrayBasedStack instead.)

d. Compile and run TestArrayBasedStack. If you see any output that fails to match your predictions, determine whether the stack is working incorrectly or your predictions are wrong. You may need to rely on a teaching assistant as you make this determination.

Exercise 4: Testing peek

One flaw in LinearTesterHelper and, therefore, in TestArrayBasedStack, is that there is no testing of the peek operation. Update both classes with some interesting tests of peek.

Exercise 5: Matching Parens

One useful application of stacks is matching things. For example, we can match the parens in a Scheme expression as follows:

Step through the characters in the expression
  When you encounter an open paren, push it on the stack
  When you encounter a close paren, pop the corresponding open paren 
    off the stack
  If you encounter a close paren with an empty stack, that close paren
    is mismatched.
If the stack is not empty, there are unmatched open parens.

Write a main class that implements this strategy for testing the validity of the parentheses in a Scheme (or arithmetic) expression. For example, you might use the following string as a test case: "( (2 + 4) * 6) / 3". Note that you do not need to check whether the expression makes sense. Just test whether the parentheses are appropriately matched.

Exercise 6: Matching Multiple Symbols

You can also use the algorithm above to match square brackets, angle brackets, and braces. However, when you encounter a close symbol, you should ensure that it matches the open symbol that you pushed on the stack (e.g., a square bracket should not close an open paren).

Update your answer to the previous exercise to check matches of parens, square brackets, angle brackets, and braces.

For Those With Extra Time

Extra 1: Matching Parens, Revisited

Revise your answer to exercise 5 to print out the locations of matching symbols. In this case, instead of pushing the open paren you should push the location of that paren (probably as an Integer).

Extra 2: Displaying Matching Parens

Extend your answer from the previous extra problem to provide a nice picture of the matching parens. For example, for each pair of matching parens, you might draw a line underneath, as in the following.

(oh (boy) (I am having) ((so) much) fun matching (parens))
    +---+
          +-----------+
	                 +--+
			+---------+
			                         +------+
+--------------------------------------------------------+