Assign3: Balanced Operators

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. Often times it is the compiler's job to determine whether or not the characters are balanced. In fact, you may have even encountered the compiler's wrath of red error text or pink highlighting the last time you had an imbalanced operator! In this part of the assignment, it will now be your job to analyze the text of a program and determine whether it has appropriately balanced bracketing operators!

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 cleaning code for the first two assignments, but in those situations you processed the string using an iterative loop. This time we want you to take a recursive approach to get practice with recursive problem-solving. In particular, you can think of approaching this problem in a similar way to what we saw in lecture with the reverse function. Processing the string can be divided into two steps:

  • Process the first character of the string and determine how (if at all) it should be kept as part of the output.
  • Recursively process the rest of the string

This function is a great way to start getting process with the core recursive problem solving logic. Be sure to thoroughly test your function before moving on. You should add at least 2-3 tests of your own to validate the behavior of your operatorsOnly function.

Next up is the checkOperators function which is also to be implemented recursively. To help get you starter, consider the following recursive insight about how to approach this problem. 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

Once you have finished implementing the function, make sure to thoroughly test its behavior. You should add at least 3-4 tests of your own to validate the behavior of your checkOperators function.

  • Q8. Compare your recursive solution to the iterative approach used for the Check Balance problem in Section 2. Which version do you find easier to read and understand? In which version did you find it easier to confirm the correct behavior?

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. As mentioned above, you will need to add student tests of your own for complete coverage. Given thorough independent testing of the operatorsOnly and checkOperators functions, 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.