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 
}

Balanced is {}()[] and any combination of that such as [()]

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

Answer 1

import java.util.*;
class Solution{

   public static void main(String []argh)
   {
      Scanner sc = new Scanner(System.in);


      while (sc.hasNext()) 
      {
         String input=sc.next();
         Stack<Character> stacky = new Stack<>();
          int x=0,y=0,z=0,a=0,b=0,c=0;
         for (int i = 0; i < input.length(); i++) 
         {

                switch(input.charAt(i)) 
                {
                    case '[' : a++; break;
                    case '{' : b++;break;

                     case '(' : c++;
                    break;

                    case ']' :x++; break;
                    case '}' : y++; break;

                     case ')' :
                            z++;
                    break;



                default: stacky.push(input.charAt(i));
          }


            //Complete the code

            if(x==a && y==b && z==c)
                {

                System.out.println("true");

                 }
             else
                 {
                 System.out.println("false");
             }




      }

   }
   }}

http://www.geekpandit.com/2016/07/25/simple-balanced-parenthesis-problem-stack-implementation/.

Answer 2

Here is the algorithm, I just tried and it works. Idea is that on every opening bracket you expect the closing one of the same type. The function above needs to be called like this isBalanced("([2+3])", 0, new Stack<Character>()). The expecting characters are maintained using stack.

public static boolean isBalanced(String s, int i, Stack<Character> expected) {
    /* end has reached and not expecting anything then break */
    if (i == s.length())
        return expected.isEmpty();

    char c = s.charAt(i);
    /* expecting something and it is a closing type */
    /* then it should match expecting type */
    if (c == '}' || c == ')' || c == ']') {
        char e = expected.isEmpty() ? '\0' : expected.pop();
        if(e != c)
            return false;
    }

    if(c == '{') 
        expected.push('}');
    else if(c == '[')
        expected.push(']');
    else if(c == '(')
        expected.push(')');

    /* call recursively with i + 1 */ 
    return isBalanced(s, i + 1, expected);

}

Here is non-stack version of code: Call is like this isBalanced2("{[]}[()]", 0, '\0') < 0 ? false : true.

public static int isBalanced2(String s, int i, char match)
{
    if(i >= s.length())
        return match == '\0' ? 0 : -1;

    char c;
    int j;
    for(j = i; j < s.length(); j++)
    {
        c = s.charAt(j); 
        /* any of the closing type */
        if(c == ']' || c == '}' || c == ')') {
            return c == match ? j : -1;
        }

        if(c == '{') 
            j = isBalanced2(s, j + 1, '}');

        else if(c == '[')
            j = isBalanced2(s, j + 1, ']');

        else if(c == '(')
            j = isBalanced2(s, j + 1, ')');

        if(j == -1)
            break;
    }

    return match != '\0' ? -1 : j;
}

Answer 3

Direct cycle is fastes solution here:

private static boolean isBalanced(String s)
{
    char[] chars = new char[s.length()];
    int size = 0;
    for (int i = 0; i < s.length(); i++)
    {
        char c = s.charAt(i);
        if (c == '{' || c == '(' || c == '[') chars[size++] = c;
        if (c == '}' && (size == 0 || chars[--size] != '{')) return false;
        if (c == ')' && (size == 0 || chars[--size] != '(')) return false;
        if (c == ']' && (size == 0 || chars[--size] != '[')) return false;
    }

    return true;
}

Complexity of algo is O(N) without substrings and etc.

Answer 4

Let's approach this formally, to increase the probability that we come up with a working solution without lots of debugging.

What's a balanced string? Here's a simple grammar:

BalancedString: Sequence end-of-string;

Sequence:
    Fragment Sequence |
    (* empty *);

Fragment:
    '(' Sequence ')' |
    '[' Sequence ']' |
    '{' Sequence '}' |
    any-character-not-in-'()[]{}';

Note that this grammar produces strings like (hello)[[good]{bye}] that have more than one "top-level" group.

Now let's turn that into a recursive-descent parser. Each nonterminal (BalancedString, Sequence, and Fragment) becomes a function. We'll start with the function that parses the 'BalancedString' non-terminal:

private static bool parseBalancedString(String input, int offset) {
    offset = parseSequence(input, offset);
    return offset == input.length();
}

Notice that this function expects parseSequence to return the offset at which it stopped parsing. Let's write parseSequence next. We'll use a loop instead of making it directly recursive.

private static int parseSequence(String input, int offset) {
    bool parseSucceeded = true;
    while (parseSucceeded) {
        int newOffset = parseFragment(input, offset);
        parseSucceeded = newOffset > offset;
        newOffset = offset;
    }
    return offset;
}

Notice that parseSequence expects parseFragment to return the offset at which it stopped parsing, and it should return the offset it was passed if it fails. Now we'll write parseFragment. We'll extract the common code from its three similar productions into a helper function.

private static int parseFragment(String input, int offset) {
    if (offset >= input.length()) {
        return offset;
    }

    switch (input.charAt(offset)) {
        case '(': return helpParseFragment(input, offset, ')');
        case '[': return helpParseFragment(input, offset, ']');
        case '{': return helpParseFragment(input, offset, '}');
        default: return offset + 1;
    }
}

The helper function expects to receive the offset of the opener, so that it can return that offset if it fails. If it succeeds, it returns the offset just past the closer.

private static int helpParseFragment(String input, int offset, char closer) {
    int newOffset = parseSequence(input, offset + 1);
    if (newOffset > offset && newOffset < input.length() && input.charAt(newOffset) == closer) {
        return newOffset + 1;
    } else {
        return offset;
    }
}

Answer 5

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.