CS140 --lab 6

Lab Objective

This lab is designed to give you experience using stacks.

Lab Materials

You will need the following files:

Part 2: balance

Write a program called balance that checks to see if parentheses, square braces and curly brackets are balanced in standard input. All other characters should be ignored. Balanced means what you think it means. The following is balanced: 
{}[ ( ) ] {{  [ []() ] }}   {
     }
Each of the following four lines is unbalanced: 
{ (}             - left paren and right curly bracket don't match
[ () }           - left square brace and right curly bracket don't match
}                - no left curly bracket
() ( [] ) (      - no right paren
If standard input is balanced, the program should print out the number of each pair seen. If not, the program should print out what the error is, and on what lines the mismatch occurred.

For example, look at the files input1, input2, input3, and input4.

Input1 is a C program where everything is balanced. (Actually, it is stacktail.c from the stack lecture.) When you run balance on it, the output should look like: 

UNIX> balance < input1
Parentheses    (): 26
Square braces  []: 3
Curly brackets {}: 5
UNIX>
Almost all C programs are balanced -- try a few: 
UNIX> balance < ~cs140/www-home/spring-2005/notes/Stacks/stackrev.c
Parentheses    (): 12
Square braces  []: 0
Curly brackets {}: 3

UNIX> balance < ~cs140/www-home/spring-2005/src/stack.c
Parentheses    (): 32
Square braces  []: 0
Curly brackets {}: 10

The other three input files have the three types of unbalances that your program needs to catch -- unmatched '(', '[' or '}', unmatched ')', ']' or '}', and mismatches. For example, input2 has three unmatched characters (read the file to see which ones): 

UNIX> balance < input2
Unmatched symbols:
  [ on line 3
  ( on line 2
  ( on line 1
UNIX>
Input3 has an unmatched right paren: 
UNIX> balance < input3
balance < input3
Unmatched ) on line 3
UNIX>
and input4 has a mismatch on lines 1 and 2 
UNIX> balance < input4
Mismatch: { on line 1 and ] on line 2
UNIX>
Obviously, the TA's will test more than just these input files. So should you.

You need to use stacks to write balance. The concept is simple -- when you see a left paren, square brace or curly bracket, you bundle up that character with its line number (i.e. you'll have to malloc() a struct) and push it on the stack. When you see a right paren, square brace or curly bracket, you first see if the stack is empty. If so, you have an unmatched character that you flag and then exit. Next, you pop a struct off the stack (you'll be using the .v field of the Jval). If the character in the struct matches the current character (for example the character in the struct is a left paren and the current character is a right paren), then you have a match, and everything is fine -- go ahead and free() the struct. If they don't match, then you have discovered a mismatch and can print it out and exit. When you are done reading standard input, if there are any structs left on the stack, then they are unmatched. If the stack is empty, you can conclude that the input was balanced.

This is a moderate-sized program -- mine was 84 lines without comments.