CS230 Lab: on Stacks

Lab: on Stacks

 

Goals:

  • Working with user-defined classes and in particular the javafoundations package
  • Implementing the Stack Interface, using
    • an array, or
    • a Vector
  • Working with Generics
  • Becoming familiar with the Vector Java class

[PRELAB]

Task 0: Vector API

Please look at the Java Vector API. In your notes, answer the following questions.

  • What package does this class belong to?
  • What are its ancestors in the hierarchy?
  • How does a vector relate to an array?
  • What are some basic methods available in the Vector class?
  • What seem to be a couple of interesting constructors in this class?

Task: ArrayStack: An implementation of the Stack Interface

Download javafoundations on your local computer. On your Desktop create a folder named lab7_startingCode and move the downloaded javafoundations folder in it.

In BlueJ, create a new project, Lab7Project and save it on your Desktop.

From the Project menu, choose Import... and browse to select lab7_startingCode, the folder that contains the javafoundations folder. (Do not double click to open the javafoundations folder!)

Your project's window in BlueJ should look like this:

Open and examine the ArrayStack.java class in the javafoundations package.

  • Is the class completely defined?
  • How do you know which methods you should still defined?

Set up a main() method to which you will later add testing code for the ArrayStack class.

At this point zip your lab7Project folder and upload it to your gradescope account. We will pick it up for there in the lab.

[END of PRELAB]

Download your pre-lab work from gradescope.

Finish the ArrayStack.java implementation. Add testing code in the main(0 method.

Task: VectorStack: Another implementation of the Stack Interface

In this task you will implement the Stack Interface using a Vector. We haven't worked with the Vector class before. Vector is a Java class, similar to an array, but much easier to use. 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 are left-shifted automatically).

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 a Driver class, named StackDriver. Where should this Driver class be saved?

Is there any code you have written that you can re-use in this class?

Task: Using Stacks (as time permits...)

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/balance. Such an expression is considered correct, if the open brackets match exactly the close brackets.

As you get started, locate and open in your browser any material relevant to this task that you may have seen/worked with in lectures or elsewhere.

The idea for this program is that you examine the given expression, character by character, maintaining a stack of brackets as follows:

  • if the current character you are examining is an open bracket, you push it onto the stack.
  • if it is a close bracket, you pop the most recent character from your stack.
  • These two characters should match each other, otherwise the expression is not valid.
  • if the current character is anything else you ignore it and just move to the next one.
  • After you examine all of the characters in the expression, without detecting any issue, you have to check the stack: if it is empty, you can tell that the original expression had balanced brackets. Otherwise, it did not.

Proceed only after you have the code in detail on your notebook, and you have tested its correctness by "running it by hand" on a few inputs.

Start by downloading this starting code.

  • Should this program be part of the javafoundations package?
  • In what directory should the program file be saved?
  • You need to use a Stack for this task. Which Stack implementation are you going to use? What options do you have?

Notice how the downloaded class is structured as an OOP program, with its

  • instance variables,
  • constructor,
  • toString() method,
  • instance methods as needed,
  • as well as some helper methods to help produce a cleaner/more high-level code at the end and
  • a main() method to test your code.
  • some of the helper methods here need to be defined by you