CS230 Lab: on Stacks

Lab: on Stacks

 

Goals:

Practice with implementing the Stack Interface, using

  • an array, and
  • a Vector

Become familiar with the Vector java class

Use a Stack ADT to match the brackets in an expression

Start working with user-defined packages of classes

 

Solutions

 

Task 1A: ArrayStack One implementation of the Stack Interface

[PRELAB]

Is the ArrayStack class, in the download/lab6/javafoundations folder complete? How do you know which methods you need to define? Write on your notebook with pencil the definitions of the missing methods. Then write testing code, again on your notebook. We will pick it up from here in lab.

[END of PRELAB]

 

Getting started

Download the lab6 folder to your Desktop. Rename it to include the names of the two partners.

 

Task 1B: ArrayStack One implementation of the Stack Interface, cont.

Relevant downloaded files in the javafoundations folder. Create Lab6Project, and import the folder that contains the javafoundations folder. You BlueJ's window should look like this:

Now edit the ArrayStack.java file, according to your notes (see pre lab), to finish this implementation and test the class.

 

Task 2: VectorStack An other implementation of the Stack Interface

In this task you will implement the Stack Interface using a Vector. We haven't seen this class before. Vector is a java class, in the util package. It is similar to array, but much easier to use, as its size grows and shrinks automatically to accommodate items as needed. Also, removing an item from a Vector is easier than doing so in an array, as the "hole" left behind is automatically filled in (items as left-shifted as needed).

Check the java API to see what methods you have available in the Vector class. Then write a class, named VectorStack, to implement the Stack Interface. Make this class part of the javafoundations package. (Can you tell why?)

Test this class in the main() method, as always.

 

Task 3: Using Stacks

In this task, you will write a program MatchChecker to check an expression that contains different kinds of bracketing (namely parentheses, square brackets, curly brackets, angle brackets) for correctness. Such an expression is considered correct, if the open brackets match exactly the close brackets.

Should this program be part of the javafoundations package? Where should this file be saved?

You need to use a Stack. Which Stack implementation are you going to use? Do you even have a choice?

The idea is that you examine the given expression, character by character, and every time you find an open bracket, you push it into a stack. Every time you find a close bracket, you take out the most recent character from your stack. These two characters should match each other, otherwise the expression is not valid. After you run through the whole expression, and if your stack is empty, you can tell that the original expression had balanced brackets.

Structure this program as an OOP program, with its instance variables, constructor, toString() method, instance methods as needed, and a main method to test your code. You will also need to define a few helper methods here, in order to keep your code clean and readable.

Add two constructors: one that takes no inputs and one that takes the string to be checked as input.

Here is some sample output:


String: *{{(:-p)}}          Balanced should be true. Program says: true

String:  a [{b(c<55>)d}f]   Balanced should be true. Program says: true

String: [{<(>)}]            Balanced should be false. Program says: false

String: a [{b(c<55>)d(f]    Balanced should be false. Program says: false

String: xyz [f r {1+3} * (23-2) {6}] Balanced should be true. Program says: true