CODEWITHSUNDEEP
javastringrecursion
user2082839
user2082839

Reputation:

Recursively check if a String is balanced

I want to check if a String has matching braces, brackets or parenthesis.

For example:
{}
()
[]

I can do it with a stack. I want to do it with recursion. I was reading the answers for a similar question and the replies were recursion mixed in with a stack. An user responded to those answers saying that recursion is also a stack so your recursive method should not have a stack in the parameters -- this makes sense to me.

I have a big problem though, I'm looking through the String backwards and always removing the last position I check until the String is empty so I return true. I can't picture how I will check for the particular parts, braces, brackets or parenthesis without having an extra parameter in my method to hold what I am looking for. Yet I keep thinking there has to be an easier way to do this.

public boolean isBalanced(String in)
{
    if(in.isEmpty())
        return true;

    if(in.charAt(in.length()) == '}')
    {
        return recIsBalanced(in.substring(0, in.length()));
    }

    else if(in.charAt(in.length()) == ']')
    {

    }


    return recIsBalanced(in.substring(0, in.length()));
}

Upvotes: 1

Views: 10891

Answers (5)

Chris
Chris

Reputation: 1

boolean isBalanced(String str)
{
    if (str.isEmpty()) {
        return true;
    }
    else if (str.charAt(0) == '(') {
        return str.charAt(str.length() - 1) == ')'
            && isBalanced(str.substring(1, str.length()));
    }
    else if (str.charAt(0) == '[') {
        return str.charAt(str.length() -  1) == ']'
            && isBalanced(str.substring(1, str.length()));
    }
    else if (str.charAt(0) == '{') {
        return str.charAt(str.length() - 1) == '}'
            && isBalanced(str.substring(1, str.length()));
    }
    else {
        return true;
    }

}

Upvotes: 0

matthieu lieber
matthieu lieber

Reputation: 662

Here is a solution, not replacing anything, straight up recursion:

/**
 * @param args
 */
public  boolean balance(String s, int start, int end)
{
   System.out.println("start:"+start + " end" + end);
   if (start == s.length()) return end == 0;
   if (end<0) return false;
   //if (end == s.length()-1) return start == 0;
   if (s.charAt(start) == '(')
     return balance(s, start+1, end+1);
   if (s.charAt(start) == ')')
     return balance(s, start+1, end-1);
   return balance(s, start+1, end );

}

Upvotes: 1

jot
jot

Reputation: 39

 public static boolean isBalanced(String str) {

    if (str.length() == 0) {
        return true;
    }
    if (str.contains("()")) {
        return isBalanced(str.replaceFirst("\\(\\)", ""));
    }

    if (str.contains("[]")) {
        return isBalanced(str.replaceFirst("\\[\\]", ""));
    }

    if (str.contains("{}")) {
        return isBalanced(str.replaceFirst("\\{\\}", ""));
    } else {
        return false;
    }
}

Upvotes: 1

Ante
Ante

Reputation: 5458

It can be done by parsing input string. Grammar for this case is:

P -> (P)
P -> [P]
P -> {P}
P -> e  (Null)

It is easier to track position what is parsed in a string, and that recursion stack holds what parenthesis to be closed. Here is simple python implementation.

ps = { '{': '}', '(': ')', '[': ']'}
all_ps = set(['{', '}', '(', ')', '[', ']'])
read_position = 0

def _is_balanced( s, closing_par=None ):
  global read_position
  while read_position < len(s):
    if s[read_position] == closing_par:
      read_position += 1         # Read closing parenthesis
      return True
    elif s[read_position] in ps:
      read_position += 1         # Read opening parenthesis
      if not _is_balanced( s, ps[s[read_position-1]] ):
        return False
    else:
      if s[read_position] not in all_ps:
        read_position += 1       # Read non-parenthesis char
      else:
        return False            # It is closing parenthesis, witouh opening before
  return closing_par is None    # Are we looking for a closing parenthesis?

def is_balanced( s ):
  global read_position
  read_position = 0  # Reset parsing position
  return _is_balanced( s )

Upvotes: 0

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70999

Easiest way to solve this problem using recursion is to shrink the string from both directions. You iterate from left and from right until you see . If these do not match, String is not balanced otherwise apply same algorithm for the String enclosed between those braces. Going only from one end will be a lot trickier and you will have to store some state.

EDIT: thanks to DanielFischer. Actually iterate from one side e.g. left until you find a brace(if this brace is not opening one return false). Than iterate from the other side(in this case right) until you find a matching brace. Now the string will be balanced if and only if the substring enclosed within this braces is balanced and the string to the right of the closing bracket are both balanced using recursion.

Upvotes: 3

Related Questions