Vérifier si une chaîne donnée est équilibré entre parenthèses de la chaîne, de manière récursive

J'ai de la difficulté comme un débutant en java (et de la programmation à tous) avec une mission qui nous a été donné. La mission est divisée en 3 parties, pour vérifier si une chaîne donnée a équilibré entre parenthèses.

Les "règles" sont comme suit:

  • "abcdefksdhgs" - est équilibré
  • "[{aaa<bb>dd}]<232>" - est équilibré
  • "[ff{<gg}]<ttt>" - n'est PAS équilibré ( pas de fermeture pour " <' )
  • "{<}>" - n'est PAS équilibré

La 1ère partie de la mission était d'écrire une méthode qui vous permettra d'obtenir un tableau de char contenant une chaîne de caractères,
et va trouver le PREMIER indice (= array cellule) contenant un support, l'une des opérations suivantes:

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

Que, bien sûr, était facile à faire:

/**
 * 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

La 2ème partie a été d'écrire une méthode qui vous permettra d'obtenir deux caractères, et retourne true seulement si le second char est approprié crochet de fermeture de la première char (exemple: 1er= "< "2e=" >' = vrai (l'inverse est faux!), 1er= "< " 2e='e' = false ). C'était aussi pas mal:

/**
 * 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

La 3ème partie est d'écrire une méthode RÉCURSIVE, qui permettra d'obtenir une chaîne de caractères et retourne "true"
si et seulement si la chaîne est équilibré support de chaîne. Bien sûr, nous devons utiliser les 1er&2e méthodes que nous avons écrit, et aussi on nous a donné une astuce:

ASTUCE: utiliser une aide de la méthode, qui vous permettra d'obtenir 2 chaînes

Sur cette partie, je suis coincé. Je suis venu avec plusieurs arrêt de cas:

  1. si il n'y a pas de support dans la chaîne - return true
  2. si la chaîne est vide, renvoyer la valeur true (cette option est couvert dans la 1ère méthode)
  3. si ouverte d'un support et d'un crochet de fermeture correspondant - return true

sinon, retourne false.
dans le code de l'écriture elle-même, je suis actuellement coincé et ne savent pas comment continuer à partir de l'appel récursif en ligne 26 dans mon code pour cette méthode:

/**
 * 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

Je ne sais pas comment continuer si le récursive code de la ligne 26 retournera true.

Je vais être heureux d'obtenir quelques conseils de la part des experts ici, dans quelle direction aller, ou je suis en train de faire tout faux depuis le début.

Je pense que vous n'avez pas compris l'astuce. C'est dire que la principale fonction qui prend un argument et renvoie une valeur booléenne n'a pas besoin d'être récursive lui-même, mais plutôt qu'il doit avoir une récursif de la fonction d'assistance qui prend deux chaînes de caractères (et renvoie tout ce qui est pratique pour sa mise en œuvre, peut-être un index entier, ou une autre chaîne).

OriginalL'auteur Adiel | 2013-12-10