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.)

* 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. I suppose “and” could also be used here, but I think this “or” is well within the bounds of colloquial usage (and, frankly, rather implied by the use of the term “flexible”). Those who are especially keen to be accurate might acquaint themselves with Jean-Yves Girard’s Linear Logic and its resource-sensitive, game-theoretic-flavored splitting of the notions of choice and combination into what are ultimately four different conjunction and disjunction operators. For details see, e.g., this exposition by Patrick Lincoln, especially the vending-machine example and “Lafont’s café”. (See also pages 8 and following in Pierre-Louis Curien’s Introduction to linear logic and ludics, Part I.) Modern students will have to be tolerant of the cigarettes used in the former analogy: it was a more innocent time! Furthermore, the culturally-sensitive student should make allowances for (and celebrate!) the Gallic background of the original author.

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?)

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 empty )
        generate an error (too many right brackets)
        generate success! (the brackets all match correctly)

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.