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.
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.)
* The sense of “or” used here is intended to be such that your program can read either from a console or from a file, meaning that the choice should be available to the user.
Write up the following interfaces and classes for stacks in Java, along with one main program class (the bracket checker).
Stack which includes operations for pushing,
popping, and checking for empty;
ArrayStack which implements the Stack
interface using ArrayLists;
ListStack which implements the Stack interface
using a linked list (you can base this and the related Node class
on the examples we developed in lecture).
Node which implements a basic linked list node
with a single item and a single reference to a next node;
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.)
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?)
Or, to be very explicit about it, you can accomplish the matching process according to this pseudo-code:
for( every input character c ) { if( c is a left bracket ) push(c) // on the stack else { if( c is a right bracket ) { if( the stack is empty ) generate an error (too many right brackets) else { match( c against the popped left bracket ) // for shape if( they don't match ) generate an error (bracket mis-match) (or just keep going if they do match) } } } // no need to do anything for non-bracket characters! } // when the for loop is done (no more characters) if ( the stack is NOT* empty ) generate an error (too many *left* brackets) else generate success! (the brackets all match correctly)
* Special thanks and a hat-tip to Alex for pointing out the need for the NOT here!
Note that this “code” will shrink down considerably when actually
written up in Java. For example, if you generate errors by using a return
statement, some of the else branches will become unnecessary, as there
will be no possibility of continuing past the return. You might also
use a switch statement to distinguish between left brackets, right
brackets, and other (non-bracket) characters.