CS230 Data Structures, Wellesley College

[CS230 Home Page][Syllabus] [Students][ Assignments][Documentation] [CSDept.] [CWIS]

Lab 5

Task 1

Stack Implementation using a Vector

In the lecture recently you heard about the Stack ADT. In cs230 this semester we are using a home-grown Stack Interface , as oppose to the java provided Stack class .

Today in lab, we will implement the Stack Interface , using a Vector as the container of the objects in the Stack. To get started, you will download the Stack.java and StackIterator.java files from the cs230 download directory. Study the Stack.java Interface to decide what methods you need to implement. The implementaton details are up to you. However, you need to use a Vector in this implementation. Think of any decisions that you need to make before you start working on code!

Task 2

Checking for Balanced Braces in a String
(If you have more time...)

Here is an example of balance braces: a{b(c)[d]e{f}}

A useful application of stacks is exactly that: to check for balanced braces in an input string.

The idea is rather simple:

You keep a Stack of braces, and every time you encounter an open brace, you push it into your stack. Every time you encounter a close brace, you pop the top element from your stack. At the end, you ckeck your stack for being empty. If so, indeed your input string contained balanced braces. Otherwise, it didn't.

Try to refine the basic idea, and start working on its implementation, as time permits.