Basic Recursion, Check Balanced Parenthesis

Question

I've written software in the past that uses a stack to check for balanced equations, but now I'm asked to write a similar algorithm recursively to check for properly nested brackets and parenthesis.

Good examples: () [] () ([]()[])

Bad examples: ( (] ([)]

Suppose my function is called: isBalanced.

Should each pass evaluate a smaller substring (until reaching a base case of 2 left)? Or, should I always evaluate the full string and move indices inward?

Answer 1

First, to your original question, just be aware that if you're working with very long strings, you don't want to be making exact copies minus a single letter each time you make a function call. So you should favor using indexes or verify that your language of choice isn't making copies behind the scenes.

Second, I have an issue with all the answers here that are using a stack data structure. I think the point of your assignment is for you to understand that with recursion your function calls create a stack. You don't need to use a stack data structure to hold your parentheses because each recursive call is a new entry on an implicit stack.

I'll demonstrate with a C program that matches ( and ). Adding the other types like [ and ] is an exercise for the reader. All I maintain in the function is my position in the string (passed as a pointer) because the recursion is my stack.

/* Search a string for matching parentheses.  If the parentheses match, returns a  * pointer that addresses the nul terminator at the end of the string.  If they  * don't match, the pointer addresses the first character that doesn't match.  */ const char *match(const char *str) {         if( *str == '\0' || *str == ')' ) { return str; }         if( *str == '(' )         {                 const char *closer = match(++str);                 if( *closer == ')' )                 {                         return match(++closer);                 }                 return str - 1;         }          return match(++str); } 

Tested with this code:

    const char *test[] = {             "()", "(", ")", "", "(()))", "(((())))", "()()(()())",             "(() ( hi))) (())()(((( ))))", "abcd"     };      for( index = 0; index < sizeof(test) / sizeof(test[0]); ++index ) {             const char *result = match(test[index]);              printf("%s:\t", test[index]);             *result == '\0' ? printf("Good!\n") :                     printf("Bad @ char %d\n", result - test[index] + 1);     } 

Output:

(): Good! (:  Bad @ char 1 ):  Bad @ char 1 :   Good! (())):      Bad @ char 5 (((()))):   Good! ()()(()()): Good! (() ( hi))) (())()(((( )))):    Bad @ char 11 abcd:       Good! 

Answer 2

There are many ways to do this, but the simplest algorithm is to simply process forward left to right, passing the stack as a parameter

FUNCTION isBalanced(String input, String stack) : boolean   IF isEmpty(input)     RETURN isEmpty(stack)   ELSE IF isOpen(firstChar(input))     RETURN isBalanced(allButFirst(input), stack + firstChar(input))   ELSE IF isClose(firstChar(input))     RETURN NOT isEmpty(stack) AND isMatching(firstChar(input), lastChar(stack))       AND isBalanced(allButFirst(input), allButLast(stack))   ELSE     ERROR "Invalid character" 

---

Here it is implemented in Java. Note that I've switched it now so that the stack pushes in front instead of at the back of the string, for convenience. I've also modified it so that it just skips non-parenthesis symbols instead of reporting it as an error.

static String open  = "([<{"; static String close = ")]>}";  static boolean isOpen(char ch) {     return open.indexOf(ch) != -1; } static boolean isClose(char ch) {     return close.indexOf(ch) != -1; } static boolean isMatching(char chOpen, char chClose) {     return open.indexOf(chOpen) == close.indexOf(chClose); }  static boolean isBalanced(String input, String stack) {     return         input.isEmpty() ?             stack.isEmpty()         : isOpen(input.charAt(0)) ?             isBalanced(input.substring(1), input.charAt(0) + stack)         : isClose(input.charAt(0)) ?             !stack.isEmpty() && isMatching(stack.charAt(0), input.charAt(0))               && isBalanced(input.substring(1), stack.substring(1))         : isBalanced(input.substring(1), stack); } 

Test harness:

    String[] tests = {         "()[]<>{}",         "(<",         "]}",         "()<",         "(][)",         "{(X)[XY]}",     };     for (String s : tests) {         System.out.println(s + " = " + isBalanced(s, ""));     } 

Output:

()[]<>{} = true (< = false ]} = false ()< = false (][) = false {(X)[XY]} = true