Lab #6: Using Stacks to Balance Brackets

Assigned: Wed 31 March 04
Due: Mon 5 March 04

---

Checking for balanced brackets (and braces, and parentheses)

A simple application of stacks is to check for balanced pairs of delimiters. Examples of such delimiters abound in programming, including multi-line comments (with "/*" and "*/"), parentheses in expressions, braces used for statement blocks, etc. The program you write should read in single lines provided by the user (say via the console or a dialog box) and state whether or not the line consists of a properly nested string of brackets. Here the term "brackets" actually refers to any of parentheses, "curly braces" and "square brackets", which may be mixed together on the same line. Officially, the definition is:

A string of brackets is proper if each left bracket is matched by a later right bracket of the same shape, and if the intervening brackets between any matched pair also form a proper string of brackets. In this context, brackets "of the same shape" include parentheses "()" and braces "{}" as well as the traditional square kind "[]".

By way of example, the following strings of brackets are proper:

• ( ) [ ] { }
• (())[()] {([]([{}[]]))[]}

These strings of brackets are not proper:

• )(
• (]
• ([)]
• {[])}
• ([]) {( )} [

The simple algorithm to check for proper bracket nesting was described in lecture: use a stack to push left brackets when you see them, and when you see a right bracket, pop from the stack and make sure the left bracket at the top matches your current right bracket (spaces can just be skipped over). You will need to use either the Character wrapper class or something similar in order to use the stacks on characters (individual character values of type char are not objects, but just values of a primitive data type).

Blank spaces should be allowed in the input, but ignored for the purposes of matching. If any characters except brackets (of all three kinds) and spaces appear in the input, you may consider this an error and report it.

You may write your own implementation of stacks for the lab, or use any that you can find publicly available (but please don't use ones provided by other students).

Your program should be able to accommodate repeated inputs from the user (you may either provide a "Quit" button or just let the user close the window when finished).