Stacks and queues exercises

COM 1201 – Spring 2003 – Jeff Raab

Introduction

In this exercise set you will write code that implements the Stack and Queue ADTs, and code that uses those structures to perform arithmetic expression evaluation. You must follow the course guidelines for type- or handwritten answers, diagrams, and writing code, as posted on the course website.

Programming exercises

1. Write a class named VectorStack that uses the Proxy design pattern to implement the given IStack interface. Your class must delegate as much of the work of the required methods as possible to a Java Vector object.

Add tests to the StacksAndQueuesTests class that thoroughly test each of the methods of this class, in all cases you can identify.

2. Modify the createStack method in the StacksAndQueuesFactory class so that it produces a VectorStack object that represents an empty list. Run the application and click the RunRPNEvaluator button to use your class as part of an arithmetic expression evaluator.

3. Write a class named CircularArrayQueue that implements the given IQueue interface by storing elements in a dynamic, circular array. A circular array a is one where index 0 is treated as if it were immediately after index a.length – 1, and index a.length – 1 is treated as if it were immediately before index 0. This behavior has to be imparted by you, just like a dynamic array imparts the behavior of growing and shrinking on an array that is not capable of doing so on its own.

Imparting this circular nature to a Java array ensures that the only time that you will have to copy any element from one array location to another is when you grow or shrink the array holding the elements. Your class must not copy any elements from index to index except when changing the size of the array.

You must create protected methods in your class that return whether or not the queue is in a state that indicates it should grow or shrink. The first of these methods must return true if the queue is full, or false otherwise. The second of these methods must return true if the array has a length greater than 4 and is less than 1/3 full, or false otherwise. Use these helper methods in the enqueue and dequeue methods.

You must create private methods in your class that do the work of growing and shrinking the array. The first of these methods must replace the array with a new array of twice the length, and copy all of the elements to this new array. The second of these methods must replace the array with a new array of half the length, and copy all of the elements to this new array. Use these helper methods in the enqueue and dequeue methods.

Add tests to the StacksAndQueuesTests class that thoroughly test each of the methods of this class, in all cases you can identify.

4. Modify the createQueue method in the StacksAndQueuesFactory class so that it produces a CircularArrayQueue object that represents an empty queue. Run the application and click the RunRPNEvaluator button to use your class as part of an arithmetic expression evaluator.

5. Write a class named MyRPNEvaluator that implements the given IRPNEvaluator interface. This interface contains just one method, evaluate, that takes a String as input and produces an int. This method must parse the given String, store the tokens it contains, then evaluate the tokens in the expression and produce an int. Details about each of these steps are given below.

An RPN expression is an arithmetic expression in Reverse Polish Notation format. Details of this format are given in the textbook, so I won’t repeat them here.

To parse a String means to extract the meaningful information from it. Usually parsing involves ignoring formatting information and storing the meaningful information, and in this case that is what you must do. An input String to the evaluate method will look like this:

1,2,+,3,*,4,5,-,6,/

Each operand and operator is separated by a single comma. The commas can’t be left out of the String, because there would be no way to tell the successive operands 1 and 2 apart from a single operand 12. Although the commas are necessary for formatting, they can be ignored when the String is parsed into its tokens. A token is one bit of the meaningful information in the String. In the above example there are 10 tokens: 6 operands and 4 operators.

You must write a method named parseExpression that parses the given String and stores an object representing each token, in order, in a queue. You may make the IQueue object that holds these tokens part of the data definition for the class, or you may have the parseExpression method produce the IQueue object. To create an empty queue, call the following factory method:

StacksAndQueuesFactory.createQueue()

Java provides a class named StringTokenizer that makes it easy to parse Strings that have a simple format. You may either use an object of that type to make the work of parsing easier, or write the code yourself. Either is acceptable.

You will notice that the queue stores and retrieves objects, but the tokens are text. You could store String objects as tokens, but that would not be very helpful to the process of evaluating the expression. You must store each operand as a Java Integer object, and each operator as an implementation of the given IOperator interface.

Each operand must be stored as an Integer, but the expression contains only text. You must write a method named parseNumber that takes in a String as input and produces an Integer object whose int value is represented by the given text. There are several ways to write this method, and I will leave it up to you to figure out the details. A hint: check the Java HTML documentation to see if Java already provides a way to do it.

Each operator must be stored as an IOperator, but the expression contains only text. You must store an appropriately defined IOperator implementation for each operator in the expression. There are two ways that you can implement the IOperator interface for this exercise. You can either write a method that defines an anonymous inner class and returns an object of that type:

private IOperator createAddOperator() {

new IOperator() {

public Integer apply(Integer left, Integer right)

{

return new Integer(

left.intValue() + right.intValue());

}

};

}

Or, since there are exactly 4 operators, you can define the anonymous inner class and store an object of that type in the data definition for the class:

private IOperator addOperator = new IOperator() {

public Integer apply(Integer left, Integer right) {

return new Integer(

left.intValue() + right.intValue());

};

Either technique is acceptable.

Once you have written the parseExpression method, you will be prepared to write the rest of the evaluate method required by the IRPNEvaluator interface. After the expression has been parsed into tokens, the tokens must be processed in order, to evaluate the expression. The textbook describes the algorithm for doing so, and I won’t repeat it here. You may use as much of the code in the textbook as makes sense for the assignment; if you do so just cite the textbook in the top documentation comment for the class.

To evaluate the expression you will need to use a stack. You may make this IStack object part of the data definition for the class, or you may define it locally in the evaluate method. To create an empty stack, call the following factory method:

StacksAndQueuesFactory.createStack()

In order to evaluate the expression stored as tokens in the queue, you will need to be able to tell apart the operators and operands on the queue. The queue methods produce data of type Object, which does not help you tell apart the Integer and IOperator objects that are actually on the queue. You will have to use the instanceof keyword to know which kind of object was produced by the dequeue method of the queue each time it is called.

When the token queue is empty, evaluation is complete. If the expression was correctly formatted – not only in terms of the commas, but also the number of operators, operands, and their order – then the only object left on the stack will be the result of the evaluation. The int value of this Integer object is what your evaluate method must produce.

Add tests to the StacksAndQueuesTests class that thoroughly test the method of this class, in all cases you can identify.

Search for “RPN expression evaluation” on the web for more hints and details.

6. Modify the createRPNEvaluator method in the StacksAndQueuesFactory class so that it produces a MyRPNEValuator object. Run the application and click the RunRPNEvaluator button to see how your evaluator behaves for different expressions.

Extra credit

E1. Write a class named MyInfixToRPN that implements the given IInfixToRPN interface. This interface contains just one method, translate, that takes a String as input and produces a String. This method must produce the RPN expression that corresponds to the given infix arithmetic expression.

Submission

You must submit the following written and/or printed material:

• Printouts of classes and tests you wrote for programming problems

You must submit the following electronic material:

• A folder containing all of the provided files in the exercise

• Classes and tests you wrote for programming problems

Details for electronic submission are given on the course website.