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:
- si il n'y a pas de support dans la chaîne - return true
- si la chaîne est vide, renvoyer la valeur true (cette option est couvert dans la 1ère méthode)
- 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.
OriginalL'auteur Adiel | 2013-12-10
Vous devez vous connecter pour publier un commentaire.
L'idée est de garder une liste de l'ouverture des crochets, et si vous trouvez un de clôture brackt, vérifier si elle ferme le dernier ouvert:
Lorsque la chaîne est enfin vide, si la liste des brackes est vide (donc tous les brackes a été fermé) retour
true
, d'autrefalse
ALGORITHME (en Java):
TEST:
SORTIE:
Remarque que j'ai importé les classes suivantes:
Super! Pour sûr que vous pouvez utiliser aussi une chaîne de caractères comme une pile pour la sauvegarde de l'ouverture des crochets. La bonne mise en œuvre!
OriginalL'auteur Luca Mastrostefano
Votre support indice est un lieu de départ idéal, mais, je pense que vous avez besoin d'un peu plus de composants.
Tout d'abord, vous devez être en mesure de vérifier qu'une petite partie de la chaîne. Donc, votre signature doit être
checkBalanced(String str, int start, int end)
. Lorsque vous démarrez une chaîne abord, il seraitcheckBalanced(String str) { return checkBalanced(str,0,str.length()-1; }
comme la "petite section", il commence par se trouve être l'ensemble de la chaîne.Je commence à l'avant de la chaîne et de trouver de la première tranche. J'ai ensuite commencer à partir de là et de travailler jusqu'à ce que je frappe à la bonne accolade de fermeture de la première tranche. Si je l'ai fait par le biais de la chaîne sans les accolades, je retourne true. Si je l'ai fait par le biais de la chaîne et a trouvé une accolade de fermeture avant, j'ai trouvé une accolade ouvrante, je retourne false. Ce sont votre base-cas, et sont nécessaires dans tout algorithme récursif.
Si j'ai trouvé le corset comme prévu, je lance mon checkBalanced sur la sous-chaîne entre les deux, et je checkBalanced sur la sous-chaîne à partir immédiatement après l'accolade fermante à la fin de la chaîne. (À noter que "la fin de la chaîne" n'est pas de la chaîne.longueur(), mais plutôt la fin de l'index qui a été passé. Nous ne se soucient que de la gamme transmis à la méthode que nous, nous sommes dans la méthode.) Ce sont vos réelles récurrences, et dans ce cas, vous en avez deux.
OriginalL'auteur corsiKa
Utiliser regexp. Si il y a des phénomènes comme ceci:
<bb>
, (pas de parenthèses à l'intérieur) remettez à zéro de la chaîne, répétez jusqu'à ce succès. Comme ça:De sortie:
OriginalL'auteur Sergey Fedorov
OriginalL'auteur sai tvs
Vous pouvez utiliser une Pile pour garder une trace de la prochaine correspondant support prévu. Le code suivant fonctionne:
OriginalL'auteur Ling Zhong