Check if a given string is balanced brackets string, recursively

Viewed 12209

I am having trouble as a newbie in java (and programming at all) with an assignment that was given to us. The assignment is divided to 3 parts, to check if a given string has balanced brackets.

The "rules" are as follows:

  • "abcdefksdhgs" - is balanced
  • "[{aaa<bb>dd}]<232>" - is balanced
  • "[ff{<gg}]<ttt>" - is NOT balanced ( no closure for '<' )
  • "{<}>" - is NOT balanced

The 1st part of the assignment was to write a method that will get a char array containing a string, and will find the FIRST index (= array cell) containing a bracket, one of the following:

} , { , ] , [ , ( , ) , > , <  

That of course was easily done:

/**
 * bracketIndex - 1st Method:
 * this method will get a single string (read from the text file),
 * and will find the first index char that is any bracket of the following: },{,],[,(,),>,<
 * @param str1 - the given string.
 * @return index - the first index that contains character that is one of the brackets listed above.
 */
public static int bracketIndex(String str1){
        int index = -1; // default value: didn't find any bracket in the string.
        int i = 0;
        for( i = 0; i < str1.length(); i++ ){
                if(str1.charAt(i) == '}' || str1.charAt(i) == '{' || str1.charAt(i) == ']' || str1.charAt(i) == '[' || str1.charAt(i) == '(' || str1.charAt(i) == ')' || str1.charAt(i) == '>' || str1.charAt(i) == '<'){
                        return index = i;
                }//if
        }//for
        return index;
}//end of bracketIndex

The 2nd part was to write a method that will get two chars, and return true only if the second char is the appropriate closing bracket of the first char (example: 1st='<' 2nd='>' = true (opposite is false!), 1st='<' 2nd='e' = false ). That was also no trouble:

/**
 * checkBracket - 2nd Method:
 *
 * @param firstChar, secondChar - two chars.
 * @return True - if the the two chars are brackets, in which the second char is the closing bracket of the first char
 */
public static boolean checkBracket(char firstChar, char secondChar){
        if (    (firstChar == '(') && (secondChar == ')') ||
                        (firstChar == '[') && (secondChar == ']') ||
                        (firstChar == '{') && (secondChar == '}') ||
                        (firstChar == '<') && (secondChar == '>')   ){
                return true;
        }//if
        return false;
}//end of checkBracket

The 3rd part is to write a RECURSIVE method, that will get a string, and will return "true" if and only if the string is balanced bracket string. Of course we need to use 1st&2nd methods we've written, and also we were given an hint:

HINT: use an aid method, that will get 2 strings

On this part I'm stuck. I've come up with several stop cases:

  1. if there is no bracket at all in the given string - return true
  2. if the given string is empty return true (this option is covered in the 1st method)
  3. if found open bracket, and a matching closing bracket - return true

otherwise, return false. in the code writing itself, i'm currently stuck and don't know how to continue from the recursive calling in line 26 in my code for this method:

/**
 * checkBalance - 3rd Method:
 * will check if a given string is a balanced string.
 * @param str1 - the given string to check.
 * @return true - if the given string is balanced, false - if the given string isn't balanced.
 */
public static boolean checkBalance(String str1){
        boolean ans;
        int a = bracketIndex(str1);
        if ( a == -1 ){
                return ans = true;
        }//if
        if( str1.charAt(a) == '{' ||
                        str1.charAt(a) == '[' ||
                        str1.charAt(a) == '<' ||
                        str1.charAt(a) == '('   ){
                int b = bracketIndex(str1.substring(a))+1 ;
                if( b != 0 ){
                        if( checkBracket ( str1.charAt(a), str1.charAt(b) ) == true ){
                                return ans = true;
                        }//if
                        if( str1.charAt(b) == '{' ||
                                        str1.charAt(b) == '[' ||
                                        str1.charAt(b) == '<' ||
                                        str1.charAt(b) == '('   ){
                                checkBalance(str1.substring(b-1));
                        }//if
                        else{
                                return ans = false;
                        }//else
                }//if
        }//if
        return ans = false;
}//end of checkBalance

I don't know how to continue if the recursive code from line 26 will return true.

I'll be glad to get some guidance from the experts in here, on which direction to go, or I'm doing it all wrong from the start.

5 Answers
Related