Basic Recursion, Check Balanced Parenthesis

Question

Greetings all,

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

I would say this depends on your design. You could either use two counters or stack with two different symbols or you can handle it using recursion, the difference is in design approach.

Answer 2

It doesn't really matter from a logical point of view -- if you keep a stack of all currently un-balanced parens that you pass to each step of the recursion, you'll never need to look backwards, so it doesn't matter if you cut up the string on each recursive call, or just increment an index and only look at the current first character.

In most programming languages, which have non-mutable strings, it's probably more expensive (performance-wise) to shorten the string than it is to pass a slightly larger string on the stack. On the other hand, in a language like C, you could just increment a pointer within the char array. I guess it's pretty language-dependent which of these two approaches is more 'efficient'. They're both equivalent from a conceptual point of view.

Answer 3

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

Answer 4

It should be a simple use of stack ..

private string tokens = "{([<})]>";        
    Stack<char> stack = new Stack<char>();   

    public bool  IsExpressionVaild(string exp)
    {
        int mid = (tokens.Length / 2)  ;  

        for (int i = 0; i < exp.Length; i++)
        {
            int index = tokens.IndexOf(exp[i]);
            if (-1 == index) { continue; }

            if(index<mid ) stack .Push(exp[i]);
            else 
            {
                if (stack.Pop() != tokens[index - mid]) { return false; }       

            }          

        }
        return true;       

    }

Answer 5

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!