Comment pouvons-nous faire correspondre un ^ nb ^ n avec une regex Java?

La réponse est inutile de dire oui! Vous pouvez très certainement écrire un modèle de regex Java correspondant à un ⁿ b ⁿ . Il utilise une recherche positive pour l’assertion et une référence nestede pour le “comptage”.

Plutôt que de donner immédiatement le modèle, cette réponse guidera les lecteurs tout au long du processus de détermination. Diverses indications sont données au fur et à mesure que la solution est construite lentement. Dans cet aspect, j’espère que cette réponse contiendra beaucoup plus que juste un autre modèle de regex soigné. Espérons que les lecteurs apprendront également à «penser en regex» et à harmoniser les différentes constructions pour pouvoir créer plus de modèles à l’avenir.

Le langage utilisé pour développer la solution sera PHP pour sa concision. Une fois le motif finalisé, le test final sera effectué en Java.

---

Etape 1: recherche de l’assertion

Commençons par un problème plus simple: nous voulons faire correspondre a+ au début d’une chaîne, mais seulement s’il est suivi immédiatement par b+ . On peut utiliser ^ pour ancrer notre correspondance, et comme on veut seulement faire correspondre le a+ au b+ , on peut utiliser l’assertion lookahead (?=…) .

Voici notre modèle avec un harnais de test simple:

 function testAll($r, $tests) { foreach ($tests as $test) { $isMatch = preg_match($r, $test, $groups); $groupsJoined = join('|', $groups); print("$test $isMatch $groupsJoined\n"); } } $tests = array('aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb'); $r1 = '/^a+(?=b+)/'; # └────┘ # lookahead testAll($r1, $tests); 

La sortie est ( comme on le voit sur ideone.com ):

 aaa 0 aaab 1 aaa aaaxb 0 xaaab 0 b 0 abbb 1 a 

C’est exactement le résultat que nous voulons: nous faisons correspondre a+ , seulement s’il est au début de la chaîne, et seulement s’il est immédiatement suivi de b+ .

Leçon : Vous pouvez utiliser des patterns dans les vues pour faire des assertions.

---

Etape 2: Capture en temps réel (et en mode espacement libre)

Maintenant, disons que même si nous ne voulons pas que le b+ fasse partie du match, nous voulons néanmoins le capturer dans le groupe 1. De même, comme nous prévoyons avoir un modèle plus compliqué, utilisons le modificateur x pour le free-spacing. ainsi nous pouvons rendre notre regex plus lisible.

Sur la base de notre extrait de code PHP précédent, nous avons maintenant le modèle suivant:

 $r2 = '/ ^ a+ (?= (b+) ) /x'; # │ └──┘ │ # │ 1 │ # └────────┘ # lookahead testAll($r2, $tests); 

La sortie est maintenant ( comme on le voit sur ideone.com ):

 aaa 0 aaab 1 aaa|b aaaxb 0 xaaab 0 b 0 abbb 1 a|bbb 

Notez que, par exemple, aaa|b est le résultat de la join ce que chaque groupe a capturé avec '|' . Dans ce cas, le groupe 0 (c.-à-d. Ce que correspondait le motif) a capturé aaa , et le groupe 1 a capturé b .

Leçon : Vous pouvez capturer à l’intérieur d’un lookaround. Vous pouvez utiliser l’espacement libre pour améliorer la lisibilité.

---

Étape 3: Refactoring le lookahead dans la “boucle”

Avant de pouvoir introduire notre mécanisme de comptage, nous devons apporter une modification à notre modèle. Actuellement, le lookahead est en dehors de la “boucle” de répétition. C’est bien pour le moment car nous voulions juste affirmer qu’il y a un b+ suit notre a+ , mais ce que nous voulons vraiment faire est d’affirmer que pour chaque a que nous avons trouvé dans la “loop”, il y a un b correspondant .

Ne vous inquiétez pas pour le mécanisme de comptage pour l’instant et faites simplement le refactoring comme suit:

• Premier refactor a+ à (?: a )+ (notez que (?:…) Est un groupe non capturant)
• Puis déplacez le lookahead dans ce groupe non capturant
  • Notez que nous devons maintenant “sauter” a* avant de pouvoir “voir” le b+ , donc modifiez le motif en conséquence

Nous avons donc maintenant ce qui suit:

 $r3 = '/ ^ (?: a (?= a* (b+) ) )+ /x'; # │ │ └──┘ │ │ # │ │ 1 │ │ # │ └───────────┘ │ # │ lookahead │ # └───────────────────┘ # non-capturing group 

La sortie est la même qu’avant ( comme on le voit sur ideone.com ), il n’y a donc aucun changement à cet égard. L’important est que maintenant nous effectuons l’assertion à chaque itération de la “boucle”. Avec notre modèle actuel, ce n’est pas nécessaire, mais ensuite nous allons faire en sorte que le groupe 1 “compte” pour nous en utilisant la référence automatique.

Leçon : Vous pouvez capturer dans un groupe non capturant. Les regards peuvent être répétés.

---

Etape 4: C’est l’étape où nous commençons à compter

Voici ce que nous allons faire: nous allons réécrire le groupe 1 de telle sorte que:

• A la fin de la première itération du + , quand le premier a correspond, il devrait capturer b
• À la fin de la deuxième itération, lorsqu’un autre a correspond, il doit capturer bb
• À la fin de la troisième itération, il devrait capturer bbb
• …
• A la fin de la nième itération, le groupe 1 devrait capturer b ⁿ
• S’il n’y a pas assez de b pour capturer dans le groupe 1, l’assertion échoue simplement

Donc, le groupe 1, qui est maintenant (b+) , devra être réécrit en quelque chose comme (\1 b) . C’est-à-dire que nous essayons d’append un b au groupe 1 capturé lors de l’itération précédente.

Il y a un léger problème ici, car ce motif ne contient pas le “cas de base”, c’est-à-dire le cas où il peut correspondre sans référence automatique. Un cas de base est requirejs car le groupe 1 démarre “non initialisé”; il n’a encore rien capturé (même pas une chaîne vide), donc une tentative de référence automatique échouera toujours.

Il y a beaucoup de façons de contourner cela, mais pour l’instant, rendons la correspondance de référence automatique facultative , c’est-à-dire \1? . Cela peut ou peut ne pas fonctionner parfaitement, mais voyons simplement ce que cela fait, et s’il y a un problème, nous traverserons ce pont quand nous y arriverons. De plus, nous appendons d’autres cas de test pendant que nous y sums.

 $tests = array( 'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb' ); $r4 = '/ ^ (?: a (?= a* (\1? b) ) )+ /x'; # │ │ └─────┘ | │ # │ │ 1 | │ # │ └──────────────┘ │ # │ lookahead │ # └──────────────────────┘ # non-capturing group 

La sortie est maintenant ( comme on le voit sur ideone.com ):

 aaa 0 aaab 1 aaa|b # (*gasp!*) aaaxb 0 xaaab 0 b 0 abbb 1 a|b # yes! aabb 1 aa|bb # YES!! aaabbbbb 1 aaa|bbb # YESS!!! aaaaabbb 1 aaaaa|bb # NOOOOOoooooo.... 

A-ha! On dirait que nous sums vraiment proches de la solution maintenant! Nous avons réussi à faire en sorte que le groupe 1 “compte” en utilisant l’auto-référence! Mais attendez … quelque chose ne va pas avec le deuxième et le dernier cas de test !! Il n’y en a pas assez, et d’une manière ou d’une autre, ça n’a pas marché! Nous examinerons pourquoi cela s’est produit à l’étape suivante.

Leçon : L’une des façons d’initialiser un groupe autoréférencé consiste à rendre la correspondance de la référence automatique facultative.

---

Étape 4½: Comprendre ce qui a mal tourné

Le problème est que, comme nous avons opté pour la correspondance automatique, le “compteur” peut être réinitialisé à 0 lorsqu’il n’y a pas assez de b . Examinons attentivement ce qui se passe à chaque itération de notre modèle avec aaaaabbb en entrée.

  aaaaabbb ↑ # Initial state: Group 1 is "uninitialized". _ aaaaabbb ↑ # 1st iteration: Group 1 couldn't match \1 since it was "uninitialized", # so it matched and captured just b ___ aaaaabbb ↑ # 2nd iteration: Group 1 matched \1b and captured bb _____ aaaaabbb ↑ # 3rd iteration: Group 1 matched \1b and captured bbb _ aaaaabbb ↑ # 4th iteration: Group 1 could still match \1, but not \1b, # (!!!) so it matched and captured just b ___ aaaaabbb ↑ # 5th iteration: Group 1 matched \1b and captured bb # # No more a, + "loop" terminates 

A-ha! Lors de notre 4ème itération, nous pouvions toujours correspondre à \1 , mais nous ne pouvions pas égaler \1b ! Puisque nous permettons que l’appariement par référence automatique soit facultatif avec \1? , le moteur revient en arrière et a pris l’option “non merci”, ce qui nous permet alors de faire correspondre et capturer seulement b !

Notez toutefois que, sauf lors de la première itération, vous pouvez toujours correspondre à la référence automatique \1 . C’est évident, bien sûr, puisque c’est ce que nous venons de capturer lors de notre précédente itération, et dans notre configuration, nous pouvons toujours le faire à nouveau (par exemple, si nous avons capturé bbb dernière fois, nous sums bbb peut ou peut ne pas être bbbb cette fois).

Leçon : Attention aux retours en arrière. Le moteur de regex effectuera autant de retours en arrière que vous le permettez jusqu’à ce que le modèle donné corresponde. Cela peut avoir un impact sur les performances (c.-à-d. Un retour en arrière catastrophique ) et / ou sur l’exactitude.

---

Étape 5: La possession de soi à la rescousse!

Le “correctif” devrait maintenant être évident: combiner la répétition facultative avec le quantificateur possessif . C’est, au lieu de simplement ? , utilisez plutôt ?+ (rappelez-vous qu’une répétition quantifiée comme possessive ne fait pas marche arrière, même si une telle “coopération” peut entraîner une correspondance avec le modèle global).

En termes très informels, c’est quoi ?+ ? et ?? dit:

?+

• (facultatif) “Il ne doit pas nécessairement être là”
  • (possessif) “mais si c’est là, il faut le prendre et ne pas le lâcher!”

?

• (facultatif) “Il ne doit pas nécessairement être là”
  • (gourmand) “mais si c’est le cas, vous pouvez le prendre pour l’instant”
    • (retour en arrière) “mais on peut vous demander de le laisser aller plus tard!”

??

• (facultatif) “Il ne doit pas nécessairement être là”
  • (réticent) “et même si c’est vous n’avez pas à le prendre pour l’instant”
    • (retour en arrière) “mais on peut vous demander de le prendre plus tard!”

Dans notre configuration, \1 ne sera pas là la première fois, mais il sera toujours là à tout moment après, et nous voulons toujours le faire correspondre à ce moment-là. Ainsi, \1?+ Accomplirait exactement ce que nous voulons.

 $r5 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ /x'; # │ │ └──────┘ │ │ # │ │ 1 │ │ # │ └───────────────┘ │ # │ lookahead │ # └───────────────────────┘ # non-capturing group 

Maintenant, la sortie est ( comme on le voit sur ideone.com ):

 aaa 0 aaab 1 a|b # Yay! Fixed! aaaxb 0 xaaab 0 b 0 abbb 1 a|b aabb 1 aa|bb aaabbbbb 1 aaa|bbb aaaaabbb 1 aaa|bbb # Hurrahh!!! 

Voilà !!! Problème résolu!!! Nous comptons maintenant correctement, exactement comme nous le souhaitons!

Leçon : Apprenez la différence entre la répétition gourmande, réticente et possessive. Possédant facultatif peut être une combinaison puissante.

---

Étape 6: Finition des touches

Donc, ce que nous avons en ce moment est un modèle qui correspond a plusieurs fois, et pour chaque correspondance, un b correspondant est capturé dans le groupe 1. Le + termine quand il n’y a plus de a ou si l’assertion a échoué ne correspond pas à un a .

Pour terminer le travail, il suffit d’append à notre pattern \1 $ . Ceci est maintenant une référence arrière au groupe 1 correspondant, suivi de la fin de la ligne d’ancrage. L’ancre s’assure qu’il n’y a pas de b supplémentaire dans la chaîne; en d’autres termes, nous avons en fait un ⁿ b ⁿ .

Voici le modèle finalisé, avec des cas de test supplémentaires, dont un long de 10 000 caractères:

 $tests = array( 'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb', '', 'ab', 'abb', 'aab', 'aaaabb', 'aaabbb', 'bbbaaa', 'ababab', 'abc', str_repeat('a', 5000).str_repeat('b', 5000) ); $r6 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ \1 $ /x'; # │ │ └──────┘ │ │ # │ │ 1 │ │ # │ └───────────────┘ │ # │ lookahead │ # └───────────────────────┘ # non-capturing group 

Il trouve 4 correspondances: ab , aabb , aaabbb et a ⁵⁰⁰⁰ b ⁵⁰⁰⁰ . Il ne faut que 0,06s pour fonctionner sur ideone.com .

---

Étape 7: Le test Java

Le pattern fonctionne donc en PHP, mais le but ultime est d’écrire un pattern qui fonctionne en Java.

 public static void main(Ssortingng[] args) { Ssortingng aNbN = "(?x) (?: a (?= a* (\\1?+ b)) )+ \\1"; Ssortingng[] tests = { "", // false "ab", // true "abb", // false "aab", // false "aabb", // true "abab", // false "abc", // false repeat('a', 5000) + repeat('b', 4999), // false repeat('a', 5000) + repeat('b', 5000), // true repeat('a', 5000) + repeat('b', 5001), // false }; for (Ssortingng test : tests) { System.out.printf("[%s]%n %s%n%n", test, test.matches(aNbN)); } } static Ssortingng repeat(char ch, int n) { return new Ssortingng(new char[n]).replace('\0', ch); } 

Le modèle fonctionne comme prévu ( vu sur ideone.com ).

---

Et maintenant nous arrivons à la conclusion …

Il faut dire que les a* dans la tête de lecture, et même la “boucle principale + “, permettent tous deux un retour en arrière. Les lecteurs sont encouragés à confirmer pourquoi cela ne pose pas de problème en termes d’exactitude et pourquoi, en même temps, les deux possessifs pourraient également fonctionner (bien que mélanger le quantificateur possessif obligatoire et non obligatoire dans le même modèle puisse conduire à des perceptions erronées).

Il convient également de dire que bien qu’il soit intéressant qu’il y ait un modèle de regex qui corresponde à un ⁿ b ⁿ , ce n’est pas toujours la meilleure solution dans la pratique. Une solution bien meilleure consiste simplement à faire correspondre ^(a+)(b+)$ , puis à comparer la longueur des chaînes capturées par les groupes 1 et 2 dans le langage de programmation d’hébergement.

En PHP, cela peut ressembler à ceci ( comme vu dans ideone.com ):

 function is_anbn($s) { return (preg_match('/^(a+)(b+)$/', $s, $groups)) && (strlen($groups[1]) == strlen($groups[2])); } 

Le but de cet article n’est PAS de convaincre les lecteurs que regex peut presque tout faire; il est clair que cela ne peut pas, et même pour les choses qu’il peut faire, une délégation au moins partielle à la langue d’hébergement devrait être envisagée si elle conduit à une solution plus simple.

Comme mentionné en haut, alors que cet article est nécessairement marqué [regex] pour stackoverflow, il s’agit peut-être de plus que cela. Bien que l’apprentissage des assertions, des références nestedes, du quantificateur possessif, etc. soit une valeur, la plus grande leçon est peut-être le processus créatif par lequel on peut essayer de résoudre des problèmes, la détermination et le travail diverses contraintes, la composition systématique de différentes parties pour construire une solution de travail, etc.

---

Matériel bonus! Motif récursif PCRE!

Puisque nous avons fait apparaître PHP, il faut dire que PCRE prend en charge les modèles et les sous-programmes récursifs. Ainsi, le modèle suivant fonctionne pour preg_match ( comme vu sur ideone.com ):

 $rRecursive = '/ ^ (a (?1)? b) $ /x'; 

Actuellement, le regex Java ne prend pas en charge le motif récursif.

---

Encore plus de matériel bonus! Faire correspondre un ⁿ b ⁿ c ⁿ !!

Nous avons donc vu comment faire correspondre un ⁿ b ⁿ qui n’est pas régulier, mais qui est toujours dépourvu de contexte, mais pouvons-nous également correspondre à un ⁿ b ⁿ c ⁿ , qui n’est même pas dépourvu de contexte?

La réponse est bien sûr OUI! Les lecteurs sont encouragés à essayer de résoudre ce problème eux-mêmes, mais la solution est fournie ci-dessous (avec mise en œuvre en Java sur ideone.com ).

^ (?: a (?= a* (\1?+ b) b* (\2?+ c) ) )+ \1 \2 $

Étant donné que PCRE ne prend pas en charge les modèles récursifs, je voudrais juste citer l’exemple le plus simple et le plus efficace de PCRE qui décrit la langue en question:

 /^(a(?1)?b)$/ 

Comme mentionné dans la question – avec le groupe d’équilibrage .NET, les modèles du type a ⁿ b ⁿ c ⁿ

 ^ (?a)+ (?b)+ (?(A)(?!)) (?c)+ (?(B)(?!)) ... (?z)+ (?(Y)(?!)) $ 

Par exemple: http://www.ideone.com/usuOE

---

Modifier:

Il existe également un modèle PCRE pour le langage généralisé avec un motif récursif, mais une parsing préalable est nécessaire. Je ne pense pas que ce soit une traduction directe de ce qui précède.

 ^ (?=(a(?-1)?b)) a+ (?=(b(?-1)?c)) b+ ... (?=(x(?-1)?y)) x+ (y(?-1)?z) $ 

Par exemple: http://www.ideone.com/9gUwF