CS 241 Lab 3: Using Stacks to Match Brackets

This assignment follows up on an example from lecture, namely: the algorithm for matching balanced brackets in strings, using a stack (the algorithm is also described in the Weiss textbook). The coding itself is fairly straightforward, so you should be able to complete it quickly; the intent of the lab is to get you used to the idea of using multiple implementations of a data structure which support a single interface.

Two implementations of a stack interface

As we have seen by now in lecture, stacks can be supported using an interface with just a few methods (pop, push, and isEmpty; we won’t need the top method). Furthermore, we can easily implement this interface using two different data structures, namely arrays and linked lists. In order to demonstrate your understanding of these techniques, you should write an interface file called Stack and two classes which implement this interface. You will also write a main project class called BracketMatcher which will use these other interfaces and classes to solve the bracket matching problem, but in an especially flexible way.

Specifically, you should write your bracket matcher so that it uses a single stack variable of interface type Stack.

Your code should run the bracket matching algorithm twice, once using an array-based stack and once using a list-based stack. Of course, the two different runs should both agree on the status of the string (do the brackets match or not)!

Your program should also be flexible enough to read string input either from the console or from a file: in the case of console input, you should expect the entire string on one line. In the case of file input, you should prompt the user for the name of the file and read it in one line at a time until the end of the file is reached, but continuing the check through each line (i.e., carrying the contents of the stack through intact between lines) so that you check for matched brackets across the whole input file. (You may re-read the file for the second run, i.e., for the array-based or list-based stack.)

Stacks in two styles

Write up the following interfaces and classes for stacks in Java, along with one main program class (the bracket checker).

If you can, use generics in your Stack interface and implementing classes, so that they can hold any specific type of data. (See your textbook, Chapter 1, for an overview of generics.)

The bracket matcher

Your main program should check for balanced brackets in a string, using a stack. The idea is that an input string (read in from the console or from a file) will contain a mixture of parentheses (round: "()"), brackets (square: "[]") and braces (curly: "{}"), along with possibly other characters, which should be ignored. Your program should either validate that the string contains only well-nested, well-sequenced bracket pairs, or it should indicate what sort of error occurred.

For example, on input "( ()[] { [] () } )" your program would respond that the brackets (in the general sense) are all balanced properly. But on input "( [ ] { ( } ) )" you would report a mis-match at the first closing (curly) brace, since it does not match the preceding open parenthesis. On input "The (quick) [brown] {{fox()}} jumps [over{}] () the lazy ((dog))." you should also report success (since the brackets match properly and the other characters are ignored).

(How do you implement this? Simple! Just use a stack! Push every "left" bracket and make sure you can pop (off the top of the stack) a matching left bracket for each "right" one you encounter in the input. You should always find a match, never see an empty stack when matching, and end up with an empty stack at the end. (Why?)