1

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.

Daniel Widdis
  • 8,424
  • 13
  • 41
  • 63
katrina
  • 43
  • 2
  • 10
  • 1
    What do you mean when you say balanced? – user1615965 Feb 19 '13 at 03:34
  • @user1615965 by looking at the algorithm, the `String` must be balanced with `(`, `[` and `{` i.e. *(4 + [ 5 * { 6 - 1 } ] )* – Luiggi Mendoza Feb 19 '13 at 03:35
  • 1
    @djechlin When did I say I wanted anyone to code it for me? Thanks for pointing out the obvious that I am learning, I hope you feel better about yourself for trolling a noobie. – katrina Feb 19 '13 at 03:40
  • @katrina it's your responsibility to ask a precise question. "how do I do it" is not acceptable and is asking us to do it for you. This is not trolling; these are the standards anyone who posts on SO are expected to follow and they can take some time to learn. – djechlin Feb 19 '13 at 03:42
  • 1
    You return true, but not false. Odd. – Makoto Feb 19 '13 at 03:42

5 Answers5

3

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.

Makoto
  • 104,088
  • 27
  • 192
  • 230
  • I agree, the recursion would create a stack for me. What do you mean by "consume it"? Would I return something like s.substring(1) at the end of the function, that way it will be "consumed" until it is empty? – katrina Feb 19 '13 at 03:49
  • You can do it like that, but I would prefer to use a `char[]`. – Makoto Feb 19 '13 at 03:52
  • This is where I am most lost: Once I find a '(' for example, I would recursively call and pass a char match to compare? I keep trying not to pass that extra parameter, it feels weird. – katrina Feb 19 '13 at 03:58
  • Right. You'd need to send along the specific brace you're matching against. – Makoto Feb 19 '13 at 04:00
3

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;
}
Shivam
  • 2,134
  • 1
  • 18
  • 28
  • Your's returns True for System.out.println(isBalanced("[{()]", 0, '\0')); – katrina Feb 19 '13 at 05:01
  • @katrina Indeed. My logic was little off. I corrected it please look for new solution. – Shivam Feb 19 '13 at 05:18
  • I think your code should be correct now. However, your code is not going to work for long String (around a few thousand of characters). (It would also be cleaner with switch/case instead of if) – nhahtdh Feb 19 '13 at 05:23
  • I'm trying to avoid a stack though. – katrina Feb 19 '13 at 05:24
  • @katrina: You need a stack for bracket balance (in general case). – nhahtdh Feb 19 '13 at 05:25
  • @nhahtdh Yes, but everytime we have recursion we are creating a stack. So having a stack in the parameters does not make too much sense, at least to me. – katrina Feb 19 '13 at 05:27
  • @katrina: rob mayoff's answer shows how it can be done *recursively* without creating a `Stack` container. His method is quite general, therefore a bit overkill for this simple task. It can be done iteratively with a `Stack` container object. – nhahtdh Feb 19 '13 at 05:41
  • @katrina Take a look at non stacked version. If it return positive integer then `true` else `false` – Shivam Feb 19 '13 at 06:07
  • @Shivam Kalra the non stacked version returns false for "()" – katrina Feb 19 '13 at 08:44
  • @katrina last line of code `match != '0' ? -1 : j;` replace it with `match != '\0' ? -1 : j;`. It was a typo. – Shivam Feb 19 '13 at 08:50
1

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.

Толя
  • 2,839
  • 15
  • 23
0

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;
    }
}
rob mayoff
  • 375,296
  • 67
  • 796
  • 848
0
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/.

Rajat
  • 167
  • 1
  • 2
  • 10
  • [provide answers that don't require clarification from the asker](http://meta.stackexchange.com/questions/214173/why-do-i-need-50-reputation-to-comment-what-can-i-do-instead) – ddb Aug 03 '16 at 11:59