CS 241 Lab 4: Balancing Brackets with a Stack

With this lab, you’ll implement the balanced-bracket checking algorithm we discussed in lecture. But you’ll do so by first writing a Stack interface and then providing two implementations, one using arrays and one using linked lists.

Stacks in two styles

Write up the following interfaces and classes for stacks in Java, along with one project implementation (the bracket checker); you may use either implementation to test your project.

• an interface called Stack which includes the operations push, pop, isempty, isfull, size and a constructor whoops: no constructors in interfaces, of course: thanks Eoin!)
• a class called ArrayStack which implements the Stack interface using arrays ((you should have this in your notes from lecture);
• a class called ListStack which implements the Stack interface using a linked list; this will be an "adapter" that provides the Stack operations in terms of what a list provides.

Finally, you should provide a short little project which checks for balanced brackets in a string, using a stack. The idea is that an input string (read in via GUI or command line) will contain a mixture of parentheses (round: "( )"), brackets (square: "[ ]") and braces (curly: "{ }"), and that your program should either validate that it contains only well-nested, well-sequenced pairs, or indicate what sort of error happens.

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. In general, there will be other characters besides brackets and spaces—just ignore them!

The Bracket-checking Algorithm

The basic algorithm for this lab was described in lecture; it goes something like this:

• read in characters one by one;
• ignore anything that isn’t a bracket of some kind;
• push all left brackets on a stack;
• for every right bracket, make sure a left bracket of the matching kind is on the stack and pop it off;
• three kinds of errors can occur:
  1. you reach the end of the input and there are still (left) brackets on the stack;
  2. you find a right bracket in the input, but the left one on the top of the stack doesn’t match (i.e., it’s not the same kind);
  3. you try to match a right bracket with a left one from the stack, but the stack is empty;