Check if a String is balanced

Question

I want to check if a string is balanced with recursion. I found some other posts on the forum related to this question, some answers are in programming languages that I don't understand. I can do it with a stack after reading similar questions here on Stack Overflow, how do I do it recursively?

private static boolean isBalanced(String s, char match)
{
    char c;

    if(s.isEmpty())
        return true;

    for(int i = 0; i < s.length(); i++)
    {
        c = s.charAt(i); 

        if(c == '{') 
            return isBalanced(s.substring(i+1), '}');

        else if(c == '[')
            return isBalanced(s.substring(i+1), ']');

        else if(c == '(')
            return isBalanced(s.substring(i+1), ')');

        // Closing matches.
        else if(c == match)
            return true;

    }

    return 
}

Please help.

EDIT: And no I don't want anyone to code it for me, in fact, I would appriciate knowing how to do it instead. That is why I dind't understand the answers in other languages because they are too specific to that language instead of an algorithm.

EDIT2: Yes balanced is {}()[] and any combination of that such as [()]

Answer 1

The idea to doing it with recursion is the same principle with using a stack. The call stack is your LIFO structure, and you make calls in concordance with that.

Take a simple balanced String:

String bal = "(This is (perfectly) balanced.)";

First things first - let's establish our conditions.

• We don't care about anything that isn't a paren, brace, or bracket. We can disregard any character that isn't one of those three.
• If we encounter a paren, brace, or bracket, we immediately recurse and search for its match on the rest of the string. That is, if I were starting with bal, I'd recurse on bal.substring(1).

I wouldn't use a loop, since you're still traversing the entire String. I would rather consume it instead, to reduce the amount of characters I'd have to backtrack on.