Algorithme de parenthèses équilibrées en Java

1. Vue d'ensemble

Les parenthèses équilibrées, également appelées parenthèses équilibrées, sont un problème de programmation courant.

Dans ce tutoriel, nous validerons si les crochets dans une chaîne donnée sont équilibrés ou non.

Ce type de chaînes fait partie de ce que l'on appelle le langage Dyck.

2. Énoncé du problème

Un crochet est considéré comme l'un des caractères suivants - "(", ")", "[", "]", "{", "}".

Un ensemble de crochets est considéré comme une paire correspondante si un crochet ouvrant , "(", "[" et "{", apparaît à gauche du crochet fermant correspondant , ")", "]" et "} ", respectivement.

Cependant, une chaîne contenant des paires de crochets n'est pas équilibrée si le jeu de crochets qu'elle englobe ne correspond pas .

De même, une chaîne contenant des caractères sans parenthèse comme az, AZ, 0-9 ou d'autres caractères spéciaux comme #, $, @ est également considérée comme déséquilibrée .

Par exemple, si l'entrée est "{[(])}", la paire de crochets, "[]", renferme un seul crochet rond ouvrant non équilibré, "(". De même, la paire de crochets, "() ", Entoure un seul crochet fermant non équilibré,"] ". Ainsi, la chaîne d'entrée" {[(])} "est déséquilibrée.

Par conséquent, une chaîne contenant des caractères entre crochets est dite équilibrée si:

  1. Un support d'ouverture correspondant apparaît à gauche de chaque support de fermeture correspondant
  2. Les supports inclus dans les supports équilibrés sont également équilibrés
  3. Il ne contient aucun caractère autre que les crochets

Il y a quelques cas particuliers à garder à l'esprit: null est considéré comme déséquilibré, tandis que la chaîne vide est considérée comme équilibrée .

Pour illustrer davantage notre définition des parenthèses équilibrées, voyons quelques exemples de parenthèses équilibrées:

() [()] {[()]} ([{{[(())]}}])

Et quelques-uns qui ne sont pas équilibrés:

abc[](){} {{[]()}}}} {[(])}

Maintenant que nous avons une meilleure compréhension de notre problème, voyons comment le résoudre!

3. Approches de solution

Il existe différentes manières de résoudre ce problème. Dans ce didacticiel, nous examinerons deux approches:

  1. Utilisation des méthodes de la classe String
  2. Utilisation de l' implémentation Deque

4. Configuration de base et validations

Créons d'abord une méthode qui retournera true si l'entrée est équilibrée et false si l'entrée est déséquilibrée:

public boolean isBalanced(String str)

Considérons les validations de base pour la chaîne d'entrée:

  1. Si une entrée nulle est transmise, elle n'est pas équilibrée.
  2. Pour qu'une chaîne soit équilibrée, les paires de crochets ouvrants et fermants doivent correspondre. Par conséquent, il serait prudent de dire qu'une chaîne d'entrée dont la longueur est impaire ne sera pas équilibrée car elle contiendra au moins une parenthèse sans correspondance.
  3. Conformément à l'énoncé du problème, le comportement équilibré doit être vérifié entre crochets. Par conséquent, toute chaîne d'entrée contenant des caractères autres que les crochets est une chaîne non équilibrée.

Compte tenu de ces règles, nous pouvons implémenter les validations:

if (null == str || ((str.length() % 2) != 0)) { return false; } else { char[] ch = str.toCharArray(); for (char c : ch) { if (!(c == '' || c == ']' || c == ')')) { return false; } } }

Maintenant que la chaîne d'entrée est validée, nous pouvons passer à la résolution de ce problème.

5. Utilisation de la méthode String.replaceAll

Dans cette approche, nous allons parcourir la chaîne d'entrée en supprimant les occurrences de «()», «[]» et «{}» de la chaîne à l'aide de String.replaceAll. Nous continuons ce processus jusqu'à ce qu'aucune autre occurrence ne soit trouvée dans la chaîne d'entrée.

Une fois le processus terminé, si la longueur de notre chaîne est égale à zéro, toutes les paires de crochets correspondantes ont été supprimées et la chaîne d'entrée est équilibrée. Si, cependant, la longueur n'est pas égale à zéro, alors des crochets d'ouverture ou de fermeture sans correspondance sont toujours présents dans la chaîne. Par conséquent, la chaîne d'entrée est déséquilibrée.

Voyons l'implémentation complète:

while (str.contains("()") || str.contains("[]") || str.contains("{}")) { str = str.replaceAll("\\(\\)", "") .replaceAll("\\[\\]", "") .replaceAll("\\{\\}", ""); } return (str.length() == 0);

6. Utilisation de Deque

Deque est une forme de file d'attente qui fournit des opérations d'ajout, de récupération et d'aperçu aux deux extrémités de la file d'attente. Nous tirerons parti de la fonction de commande Last-In-First-Out (LIFO) de cette structure de données pour vérifier le solde dans la chaîne d'entrée.

Tout d'abord, construisons notre Deque :

Deque deque = new LinkedList();

Notez que nous avons utilisé ici une LinkedList car elle fournit une implémentation pour l' interface Deque .

Maintenant que notre deque est construit, nous allons parcourir chaque caractère de la chaîne d'entrée un par un. Si le caractère est un crochet ouvrant, nous l'ajouterons comme premier élément dans le Deque :

if (ch == '{' || ch == '[' || ch == '(') { deque.addFirst(ch); }

Mais, si le caractère est un crochet fermant, alors nous effectuerons quelques vérifications sur la LinkedList .

Tout d'abord, nous vérifions si la LinkedList est vide ou non. Une liste vide signifie que le crochet fermant ne correspond pas. Par conséquent, la chaîne d'entrée est déséquilibrée. Nous retournons donc faux .

Cependant, si LinkedList n'est pas vide, nous jetons un coup d'œil sur son dernier caractère à l'aide de la méthode peekFirst . S'il peut être associé au crochet fermant, nous supprimons ce caractère le plus haut de la liste à l'aide de la méthode removeFirst et passons à l'itération suivante de la boucle:

if (!deque.isEmpty() && ((deque.peekFirst() == '{' && ch == '}') || (deque.peekFirst() == '[' && ch == ']') || (deque.peekFirst() == '(' && ch == ')'))) { deque.removeFirst(); } else { return false; }

À la fin de la boucle, tous les caractères sont vérifiés, donc nous pouvons retourner true . Vous trouverez ci-dessous une mise en œuvre complète de l' approche basée sur Deque :

Deque deque = new LinkedList(); for (char ch: str.toCharArray()) { if (ch == '{' || ch == '[' || ch == '(') { deque.addFirst(ch); } else { if (!deque.isEmpty() && ((deque.peekFirst() == '{' && ch == '}') || (deque.peekFirst() == '[' && ch == ']') || (deque.peekFirst() == '(' && ch == ')'))) { deque.removeFirst(); } else { return false; } } } return true;

7. Conclusion

Dans ce didacticiel, nous avons discuté de l'énoncé du problème de Balanced Brackets et l'avons résolu en utilisant deux approches différentes.

Comme toujours, le code est disponible sur Github.