CS206: Data Structures, Assignment #8

Stacks and Queues

The goal of this assignment is to:

• Design an ADT, Abstract Data Type
• Implement a class to carry out the ADT design
• Develop code to test our implementation
• Solve real-world problems using the class

ADT

We will design an ADT in class to implement a Stack. It should have an interface for the following functions:

• Be able to push items onto the stack, O(1)
• Be able to pop them off the stack, O(1) [last in, first out]
• Be able to get the size of the stack (how many things it contains), O(1)
• If you attempt to pop an empty stack, an exception will be thrown
• Be able to peek at the top of the stack

Implementation

Create a Java class that implements the ADT.

Test

Write a series of tests to test each method. Test for failures and successes.

Solve Problems

Use your new stack class in another Java program to determine if the following expressions are valid. Valid expressions are made up of the following characters: "X()[]' (that is: double-quote, capital X, open paren, close paren, open bracket, close bracket, single quote, and space. Spaces can appear anywhere. If it contains a "'([ then the next non-X character must match, eg "')].

Note that if a quote or double-quote comes in, treat it as an ending, if the last on the stack is a matching quote. Otherwise, treat it as a starting symbol.

Some tests:

Think of some more problems to test your expression validator.