Computer Science 2611
Summer 1999
Laboratory 7

Balanced sequences

A sequence of parentheses, square brackets and curly braces is balanced if each left parenthesis, bracket or brace has a matching right parenthesis, bracket or brace of the same kind. For example, "{}(([]))" is balanced, but ")(", "{]" and "(()]" are not balanced. Generally, a balanced sequence must have one of the following forms, where b stands for a balanced sequence.
  1. (b)
  2. [b]
  3. {b}
  4. b b
  5. An empty sequence is balanced.

The assignment

Write a program that reads a sequence of parentheses, brackets and braces followed by a #, and tells whether the sequence is balanced. For example, on input ({})[]#, the program should say yes, and on input ))# the program should say no. If the input contains any character other than a parenthesis, bracket or brace before the #, the program should say no. For example, on input (a)#, the program should say no.

An empty sequence of characters is considered balanced. So if the input consists only of a #, then the program should say yes.

You can presume that the input contains no blanks.

Hints

Use recursion. Write a function that reads input up to a # or to the point where a balanced sequence has been read, and returns 1 if the sequence is balanced and 0 if not. For example, if the input is []()#, then calling this function once will cause the two characters [] to be read, leaving ()# unread. It will return 1.

You can read a character using operator >>, and a variable of type char. For example, 

    char c;
    cin >> c;
causes the next character to be read and put into c. (Precisely, it skips over spaces and newlines to reach the next non-white-space character, and puts that into c.)

You will find it convenient never to consume the # character until after you have read the entire input and reached a conclusion about whether it is balanced. You can use cin.peek() to get the next character without consuming it. For example, do 

   c = cin.peek();
If you do cin.peek() several times in a row, you will keep getting the same character. Unlike operator >>, peek does not skip over blanks. If you see anything but a #, then remove it from the input using operator >>. If you see a #, leave it there. Do not make it the main program's responsibility to consume the #. Think about who should have that responsibility.

Character constants are formed using single quote marks. For example, the left parenthesis character is written ')' in a C++ program.

Test your program on several inputs. Try #, ((#, )# and ()()()#, among others.