Comment Pouvons-nous faire correspondre A^N B^N avec Java regex?

La réponse est, inutile de dire, Oui! Vous pouvez certainement écrire un Java regex modèle pour correspondre à unⁿbⁿ. Il utilise un lookahead positif pour l'assertion, et une référence imbriquée pour le"comptage".

Plutôt que de donner immédiatement le modèle, cette réponse guidera les lecteurs à travers le processus de le dériver. Divers conseils sont donnés que la solution est construite lentement. Dans cet aspect, espérons que cette réponse contiendra beaucoup plus qu'un simple motif regex soigné. Espérons que les lecteurs apprendront également à "penser dans regex", et comment mettre diverses constructions harmonieusement ensemble, afin qu'ils puissent dériver plus de modèles par eux-mêmes à l'avenir.

Le langage utilisé pour développer la solution sera PHP pour sa concision. Le test final une fois le modèle finalisé sera effectué en Java.

---

Étape 1: Anticipation de l'affirmation

Commençons par un problème plus simple: nous voulons correspond à a+ au début d'une chaîne, mais seulement si elle est suivie immédiatement par b+. Nous pouvons utiliser ^ à ancre notre match, et depuis nous voulons seulement pour correspondre à la a+ sans les b+, nous pouvons utiliser anticipation affirmation (?=…).

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 vu sur ideone.com):

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

C'est exactement la sortie que nous voulons: nous correspondons à a+, seulement si c'est au début de la chaîne, et seulement si elle est immédiatement suivie de b+.

Leçon: Vous pouvez utiliser des modèles dans lookarounds pour faire des assertions.

---

Étape 2: capture dans un lookahead (et F R E e - S P A c I N G mode)

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

En nous appuyant sur notre précédent extrait de code PHP, Nous avons maintenant le modèle suivant:

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

testAll($r2, $tests);

La sortie est maintenant ( comme vu 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 join-ing ce que chaque groupe capturé avec '|'. Dans ce cas, le groupe 0 (c'est-à-dire ce que le motif correspond) capturé aaa, et le groupe 1 capturé b.

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

---

Étape 3: Refactoring du lookahead dans la "boucle"

Avant de pouvoir introduire notre mécanisme de comptage, nous devons faire une modification à notre modèle. Actuellement, le lookahead est en dehors de la "boucle" de répétition +. C'est bien jusqu'à présent parce que nous voulions juste affirmer qu'il y a un b+ suivant notre a+, mais ce que nous voulons vraiment faire finalement, c'est affirmer que pour chaque a que nous correspondons à l'intérieur de la "boucle", il y a un b correspondant pour aller avec.

Ne nous inquiétons pas du mécanisme de comptage pour l'instant et faisons simplement le refactoring comme suit:

• premier refactor a+ à (?: a )+ (notez que (?:…) est un groupe non capturant)
• déplacez ensuite le lookahead à l'intérieur de ce groupe non capturant
  • notez que nous devons maintenant "sauter" a* avant de pouvoir "voir" le b+, donc modifier le modèle 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 vu sur ideone.com ), donc il n'y a pas de changement à cet égard. La chose importante est que maintenant nous faisons l'assertion de la chaque itération de la + "boucle". Avec notre modèle actuel, ce n'est pas nécessaire, mais ensuite nous ferons le "compte" du Groupe 1 pour nous en utilisant l'auto-référence.

Leçon: Vous pouvez capturer à l'intérieur d'un groupe non capturant. Les Lookarounds peuvent être répétés.

---

Étape 4: c'est L'étape où nous commençons à compter

Voici ce que nous allons faire: nous allons réécrire le groupe 1 tel que:

• à la fin de la première itération du +, lorsque le premier a est apparié, il doit capturer b
• à la fin de la deuxième itération, lorsqu'un autre a est apparié, il doit capturer bb
• À la fin de la troisième itération, il devrait capturer bbb
• ...
• À la fin de la n-ième itération, le groupe 1 doit capturer bⁿ
• S'il n'y a pas assez de b pour capturer dans le groupe 1, l'assertion échoue simplement

Pour le groupe 1, qui est maintenant (b+), devra être réécrite de quelque chose comme (\1 b). Autrement dit, nous essayons d '"ajouter" un b à quel groupe 1 capturé dans l'itération précédente.

Il y a un léger problème ici Ce modèle manque le "cas de base", c'est-à-dire le cas où il peut correspondre sans l'auto-référence. Un cas de base est requis car le groupe 1 commence "non initialisé" ; il n'a encore rien capturé (pas même une chaîne vide), donc une tentative d'auto-référence échouera toujours.

Il y a plusieurs façons de contourner cela, mais pour l'instant, rendons simplement l'auto-référence facultative , c'est-à-dire \1?. Cela peut ou peut ne pas fonctionner parfaitement, mais voyons juste ce que cela fait, et s'il y a n'importe quel problème alors nous traverserons ce pont quand nous y arriverons. En outre, nous ajouterons d'autres cas de test pendant que nous y sommes.

$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 vu 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! Il semble que nous sommes 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 a pas assez de bs, et en quelque sorte ça comptait mal! Nous allons examiner pourquoi cela est arrivé dans l'étape suivante.

leçon: une façon d ' "initialiser" un groupe d'auto-référencement est de rendre la correspondance d'auto-référence facultative.

---

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

Le problème est que puisque nous avons rendu la correspondance d'auto-référence facultative, le "compteur" peut "réinitialiser" à 0 quand il n'y a pas assez de b. examinons de près ce qui se passe à chaque itération de notre modèle avec aaaaabbb en entrée.

 a a a a a b b b
↑
# Initial state: Group 1 is "uninitialized".
           _
 a a a a a b b b
  ↑
  # 1st iteration: Group 1 couldn't match \1 since it was "uninitialized",
  #                  so it matched and captured just b
           ___
 a a a a a b b b
    ↑
    # 2nd iteration: Group 1 matched \1b and captured bb
           _____
 a a a a a b b b
      ↑
      # 3rd iteration: Group 1 matched \1b and captured bbb
           _
 a a a a a b b b
        ↑
        # 4th iteration: Group 1 could still match \1, but not \1b,
        #  (!!!)           so it matched and captured just b
           ___
 a a a a a b b b
          ↑
          # 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 faire correspondre \1, mais nous ne pouvions pas faire correspondre \1b! Puisque nous autorisons la correspondance d'auto-référence à être facultative avec \1?, le moteur revient en arrière et a pris l'option "non merci", ce qui nous permet alors de faire correspondre et de capturer juste b!

Notez cependant que, sauf lors de la toute première itération, vous pouvez toujours correspondre uniquement à l'auto-référence \1. C'est évident, bien sûr, puisque c'est ce que nous venons de saisies sur notre itération précédente, et dans notre configuration, nous peut toujours correspondre à nouveau (par exemple, si nous avons capturé bbb la dernière fois, nous sommes garantis qu'il y aura toujours bbb, mais il peut y avoir ou non bbbb cette fois).

Leçon: Méfiez-vous des retours en arrière. Le moteur regex fera autant de retour en arrière que vous le permettez jusqu'à ce que le motif donné corresponde. Cela peut avoir un impact sur les performances (c'est-à-dire retour en arrière catastrophique) et/ou l'exactitude.

---

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

Le "fix" devrait maintenant être évident: combiner la répétition facultative avec possessif quantificateur. C'est-à-dire, au lieu de simplement ?, utilisez ?+ à la place (rappelez-vous qu'une répétition quantifiée comme possessive ne revient pas en arrière, même si une telle "coopération" peut entraîner une correspondance du modèle global).

Très informels termes, c'est ce que ?+, ? et ?? dit:

?+

• (facultatif) "il n'est pas nécessaire qu'il soit là,"
  • (possessif) " mais s'il est là, vous devez le prendre et ne pas le lâcher!"

?

• (facultatif) "il n'est pas nécessaire qu'il soit là,"
  • (gourmand) "mais si c'est que vous pouvez le prendre pour l'instant,"
    • (backtracking) "mais on vous demandera peut-être de le laisser partir plus tard!"

??

• (facultatif) "il n'est pas nécessaire qu'il soit là,"
  • (réticent) " et même si c'est le cas, vous n'avez pas à le prendre tout de suite,"
    • (backtracking) "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 être là tout le temps après, et nous toujours voulez pour le match alors. Ainsi, {[71] } accomplirait exactement ce que nous voulons.

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

Maintenant la sortie est (comme vu 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 voulons!

leçon: Apprenez la différence entre la répétition gourmande, réticente et possessive. Facultatif-possessif peut être une combinaison puissante.

---

Étape 6: finitions

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

Pour terminer le travail, nous devons simplement ajouter à notre modèle \1 $. Ceci est maintenant une référence arrière à ce que le groupe 1 correspond, suivi de la fin de l'ancre de ligne. L'ancre garantit qu'il n'y a pas de b supplémentaires dans la chaîne; en d'autres termes, qu'en fait nous avons unⁿbⁿ.

Voici le modèle finalisé, avec des cas de test supplémentaires, dont un 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

On trouve 4 matches: ab, aabb, aaabbb, et la un⁵⁰⁰⁰b⁵⁰⁰⁰. Il faut seulement 0,06 s à pour fonctionner ideone.com .

---

Étape 7: le test Java

Donc, le modèle fonctionne en PHP, mais le but ultime est d'écrire un modèle qui fonctionne dans Java.

public static void main(String[] args) {

        String aNbN = "(?x) (?:  a  (?= a* (\\1?+ b))  )+ \\1";
        String[] 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 (String test : tests) {
                System.out.printf("[%s]%n  %s%n%n", test, test.matches(aNbN));
        }

}

static String repeat(char ch, int n) {
        return new String(new char[n]).replace('\0', ch);
}

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

---

Et maintenant, nous arrivons à la conclusion...

Il faut dire que le a* dans le lookahead, et en effet la " boucle principale +", permettent tous deux de revenir en arrière. Les lecteurs sont encouragés à confirmer pourquoi ce n'est pas un problème en termes d'exactitude, et pourquoi en même temps rendre les deux possessifs fonctionnerait également (bien que peut-être mélanger les possessifs obligatoires et non obligatoires quantificateur dans le même modèle peut conduire à des perceptions erronées).

, Il faut aussi dire que tout c'est bien qu'il y a une regex modèle qui correspond à unⁿbⁿ, ce n'est pas toujours la meilleure solution dans la pratique. Une bien meilleure solution 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 est pas de convaincre les lecteurs que regex peut faire presque n'importe quoi; il ne peut clairement 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, bien que cet article soit nécessairement étiqueté [regex] pour stackoverflow, il s'agit peut-être de plus que cela. Bien qu'il y ait certainement de la valeur à apprendre sur assertions, références imbriquées, quantificateur possessif, etc, peut - être la plus grande leçon ici est le processus créatif par lequel on peut essayer de résoudre des problèmes, la détermination et le travail acharné qu'il nécessite souvent lorsque vous êtes soumis à diverses contraintes, la composition systématique de diverses parties pour construire une solution de travail, etc.

---

Matériel Bonus! Motif récursif PCRE!

Puisque nous avons soulevé PHP, il faut dire que PCRE supporte le modèle récursif et les sous-routines. Ainsi, le motif suivant fonctionne pour preg_match (comme on le voit sur ideone.com):

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

Actuellement, L'expression rationnelle de Java ne prend pas en charge le motif récursif.

---

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

Nous avons Donc vu comment le match unⁿbⁿ ce qui est un non-régulière, mais toujours libre de tout contexte, mais on peut également correspondre unⁿbⁿcⁿ, ce qui n'est même pas sans contexte?

La réponse est, bien sûr, OUI! les lecteurs sont encouragés à essayer de résoudre cela par eux-mêmes, mais la solution est fournie ci-dessous (avec implémentation en Java sur ideone.com).

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