Programming Project #1     COSC 311     WI2013

Paren matching
Distributed: 10 January 2013       Due: 22 January 2013 29 January 2013

The algorithm

The rules for properly nesting are simple:
• A left symbol -- ( [ { < -- must match a later right symbol -- ) ] } > of the same type.
• There is no practical limit to the nesting level (you can use max level 32 if you need to)
  The following are acceptable:
  • ( )
  • ( ( ( ) ) )
  • ( ( ) ( ( ) ) ( ) )
• Grouping symbols should not "cross":
  OK:
  • ( [ ] { ( ) } )
  • [ [ [ ] ] ( ) ]
  Not OK:
  • ( [ ) { ( ] } )
  • [ ( [ ) ] ]
• Other invalid strings
  • ( [ )    unmatched left
  • ( < > ) )     unmatched right

The algorithm, using a stack, to check for matched grouping symbols works as follows:

 
  while (more to do) {
  	get ch;
  	if (ch is not grouping symbol) break;
  	
  	if (ch is in left group) push it to stack;
  	
  	if (ch is in right group) {
  		if (stack is empty) exit with error notification;
  		
  		left = pop stack;
  		
  		if (left and ch do not match up) exit with error notification;
  		}
  	}				// end of while
  	
  if (stack is not empty) exit with error notification;
   

When checking for matched grouping symbols, there are four possible conclusions:

1. symbols match
2. symbols do not match up
   1. because of attempt to pop empty stack: unmatched right symbol.
   2. because left and right do not match: error is "invalid grouping"
   3. because stack is not empty when input is exhausted: error is "unmatched left symbol"

The problem

• One program to test an input stream for matching grouping symbols. For your convenience, there are no other symbols in the input stream aside from grouping characters and white space. You may have the user specify the file name, OR you can hardcode the file name.
  • If the symbols match, then output: "grouping symbols match".
  • If the symbols do not match up, then output the sort of failure (recall the three possibilities above). Once a failure is detected, the remainder of the input should not be scanned for further testing.
• One program to create randomcharacter streams (i.e., input files) that can be used to test the matching program. Note, the complete set of allowed characters comprises ONLY the grouping symbols and white space. This program should take user input for the following:
  • number of groups
  • result of matching test:
    • valid input
    • unmatched right symbol
    • invalid grouping
    • unmatched left symbol
  For extra credit, you can also let the user specify the grouping symbols (any non empty subset of {}, [], (), <>).

You must implement your own stack, including push(), pop(), and isEmpty(). The stack is implemented using a linked list (not a 1D array). You must handle popping an empty stack with grace.

IMPORTANT! You may NOT use the Java Stack class that is a part of Java 1.6 (in java.util.Stack) EXCEPT for development and debugging purposes.. You certainly can use the specification for the Java Stack in order to write your own Stack class.

Development advice

1. Write program #1 and test thoroughly. You will need input files of each type of result. Keep these input files fairly short so that it is easy to confirm that your program is working correctly.
2. Write program #2 -- test it using program #1. Start with a small number of groups.

Deliverables

• Hard copy of program #1
• Screen shot of program working correctly with the following streams:
  • ( [ ] [ ] ( { } ) ) < >       // correct
  • (                 // unmatched left symbol
  • ( ) ] ] ( )       // unmatched right symbol
  • ( ( ) { ) )       // invalid grouping
• Hard copy of program #2
• Screen shots of program working correctly to produce:
  • valid data with 3 groups
  • invalid data with 3 groups, unmatched left symbol
  • invalid data with 3 groups, unmatched right symbol
  • invalid data with 3 groups, invalid grouping.
  If you're going for the extra credit, you should produce a second set of screen shots that use only 2 of the 4 sets of grouping symbols.

Grading

• 80%: Meets the specs
• 10%: Coding style and documentation (see course site)
• 10%: Elegance

Cannibal?