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: Basic Testing
  • Exercise 2: Stack Overflow
  • Exercise 3: Fixing Stack Overflow
  • 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: 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 operations mentioned in the documentation for that class.

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

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

Note that because of an error in the Java compiler, you will get a warning in a few lines of ArrayBasedStack. You may ignore those warnings.

Exercise 2: Stack Overflow

a. Look at the code for ArrayBasedStack

b. What do you expect to happen when more then ten values are put into the stack?

c. Update TestArrayBasedStack so that more than ten values end up in the stack.

d. Run the modified code to confirm your hypothesis.

Exercise 3: Fixing Stack Overflow

As you may have just determined, the ArrayBasedStack behaves horribly if you add too many elements. Is there a solution? Certainly. As the reading suggested, when trying to add elements when no spaces are left in the array, you must

• make a new, larger array
• copy the existing elements to that array
• set this.stuff to that array
• finally add the value.

Update put to check whether the stack is full and, if so, to do the steps above. (If the stack is not full, just add as before.)

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.

Exercise 6: Matching Multiple Symbols

You can also use the algorithm above to match square brackets, angle, 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))
    +---+
          +-----------+
	                 +--+
			+---------+
			                         +------+
+--------------------------------------------------------+

History

Sunday, 6 March 2005 [Samuel A. Rebelsky]

• Created.

Tuesday, 7 March 2006 [Samuel A. Rebelsky]

• Began update.