Assign3: isBalanced

In the syntax of most programming languages, there are characters that occur only in nested pairs, which are called bracketing operators. C++, for example, has these bracketing operators:

( . . . )
[ . . . ]
{ . . . }

In a well-formed program, these characters must be properly nested and matched. To determine whether this condition holds for a particular program, you can ignore all the other characters and look simply at the pattern formed by the parentheses, brackets, and braces. In a legal configuration, all the operators match up correctly, as shown in the following correctly balanced example:

 int main() { int x = 2 * (vec[2] + 3); x = (1 + random()); }

 Operators only = (){([])(())}
 
 Yes, operators are correctly balanced!

The following strings, however, are illegal for the reasons stated:

( ( [ a ] )   The line is missing a close parenthesis.
3 ) (         The close parenthesis comes before the open parenthesis.
{ ( x } y )   The parentheses and braces are improperly nested.

The function isBalanced given below takes a string str of text and returns true or false to report whether the bracketing operators in str are balanced. The function first extracts the operator characters from str using the function operatorsOnly and then checks that those operators are balanced using the function checkOperators.

bool isBalanced(string str) {
    string ops = operatorsOnly(str);
    return checkOperators(ops);
}

Your job is to implement the two functions:

string operatorsOnly(string str);

bool checkOperators(string ops);

The operatorsOnly function returns a string consisting of only the bracketing characters from str. You implemented some similar string-processing operations for assignment 1 Soundex, but you processed the characters using an iterative loop. This time we want you to take a recursive approach. Processing the string can be divided into two steps:

• Process the first character of the string and see if it should be kept
• Recursively process the rest of the string

This function is a great warmup use of recursion. Be sure to thoroughly test your function before moving on.

Next up is the checkOperators function which is also to be implemented recursively. Code your solution so that it embodies the recursive insight that a string consisting of only bracketing characters is balanced if and only if one of the following conditions holds:

• The string is empty.
• The string contains "()", "[]", or "{}" as a substring and the rest of the string is balanced after removing that substring.

For example, the operators "[(){}]" are shown to be balanced by the following chain of calls:

checkOperators("[(){}]") -> "()" exists, so remove that and check if the rest is balanced 
  checkOperators("[{}]") -> "{}" exists, so remove that and check if the rest is balanced 
    checkOperators("[]") -> "[]" exists, so remove that and check if the rest is balanced 
      checkOperators("") -> true

• Q7. Compare your recursion solution to the iterative approach used for the check Balance problem in Section 1. Which version do you find easier to write? to read? to confirm correct?

Notes

• Both of your functions must operate recursively and should not use any loops nor any auxiliary data structures (no Stacks, Queues, Vectors, etc.)
• We have provided a few tests to get you started. You will need to add student tests of your own for complete coverage. Given thorough independent testing of operatorsOnly and checkOperators, you won't likely need much additional test coverage specific to isBalanced.
• The checkOperators function expects that the string argument contains only bracketing operators. If a client erroneously calls the function with a string that also has non-bracketing characters, checkOperators will return false. This is as is expected, as the input doesn't meet the function's stated precondition.