University of Ottawa, School of IT and Engineering, CSI1102

Lab Assignment 4: Due to be marked in your scheduled lab time, Week of April 4, 2005

The aim of this assignment is to give you practice in using abstract data types, recursion concepts, and exceptions.  These exercises are mainly based on material covered in chapters 8, 11, 12.

Question 1 [5 marks]:

Printing a string backwards can be done iteratively or recursively. To do it recursively, think of the following specification:

If s contains any characters (i.e., is not the empty string)

• print the last character in s
• print s' backwards, where s' is s without its last character

Write a test driver that prompts the user for a string, then calls method printBackwards to print the string backwards. Implement the static method printBackwards inside the test driver using the recursive strategy outlined above.

Hint: use the two methods from String class ‘charAt()’ and ‘substring’

Question 2 [10 marks]:

Sometimes it's useful to define operations on an ADT without changing the type definition itself. For example, you might want to print the elements in a stack without actually adding a method to the Stack ADT (you may not even have access to it). To explore this, use the Stack class provided by Java (in java.util) and the test program StackTest.java. Add the following static methods to the StackTest class:

• void printStack(Stack s)—prints the elements in stack s from top to bottom. When printStack returns, s should be unchanged.
• Stack reverseStack(Stack s)—returns a new stack whose elements are backwards from those in s. Again, s is unchanged.
• Stack removeElement(Stack s, int val)—returns a new stack whose elements are the same as those in s (and in the same order) except that all occurrences of val have been removed. Again, s is unchanged.

Modify the main method to test these methods.

// StackTest.java

// A simple driver to test a stack.

import java.util.Stack;

public class StackTest

{

public static void main(String[] args)

{

// Declare and instantiate a stack

Stack stack = new Stack();

//push some stuff on the stack

for (int i=0; i<10; i++)

{

Integer I = new Integer(i);

stack.push(I);

}

Integer I = new Integer(5);

stack.push(I);

// print the stack

// reverse the stack and print the reversed stack

// print the original stack again

// remove all occurrences of the value 5

// print the original stack and the new stack.

}

}

Question 3 [5 marks]:

Extend question 2 with an Exception handling capability, by raising an exception of type EmptyStackException whenever you try to print from an empty stack. Use the try-catch block when invoking the printStack method. When trying to print from an empty stack the message “Reading from an Empty Stack” should be displayed. You should fulfill the following three steps:

• Define the class EmptyStackException that derives from Exception
• Modify the necessary code in question 2 to reflect the added exception handling capability
• Add a case to the test driver that throws an EmptyStackException.