Comment vérifier qu’une chaîne est un palindrome en utilisant des expressions régulières?

C’était une question d’entretien que je n’ai pas pu répondre:

Comment vérifier qu’une chaîne est un palindrome en utilisant des expressions régulières?

ps Il y a déjà une question ” Comment vérifier si la chaîne donnée est palindrome? ” et cela donne beaucoup de réponses dans différentes langues, mais pas de réponse qui utilise des expressions régulières.

La réponse à cette question est que “c’est impossible”. Plus précisément, l’intervieweur se demande si vous avez fait attention dans votre cours de théorie computationnelle.

Dans votre cours de théorie informatique, vous avez appris sur les machines à états finis. Une machine à états finis est composée de nœuds et d’arêtes. Chaque arête est annotée par une lettre d’un alphabet fini. Un ou plusieurs nœuds sont des nœuds “acceptants” spéciaux et un nœud est le nœud “start”. À mesure que chaque lettre est lue à partir d’un mot donné, nous traversons le bord donné de la machine. Si nous nous retrouvons dans un état acceptable, nous disons que la machine “accepte” ce mot.

Une expression régulière peut toujours être traduite dans une machine à états finis équivalente. C’est-à-dire, qui accepte et rejette les mêmes mots que l’expression régulière (dans le monde réel, certains langages d’expression rationnelle permettent des fonctions arbitraires, celles-ci ne comptent pas).

Il est impossible de construire une machine à états finis qui accepte tous les palindromes. La preuve repose sur le fait que nous pouvons facilement construire une chaîne nécessitant un nombre arbitrairement grand de nœuds, à savoir la chaîne

a ^ xba ^ x (par exemple, aba, aabaa, aaabaaa, aaaabaaaa, ….)

où a ^ x est une répétition x fois. Cela nécessite au moins x nœuds car, après avoir vu le «b», nous devons compter x fois pour nous assurer qu’il s’agit d’un palindrome.

Enfin, pour revenir à la question initiale, vous pourriez dire à l’intervieweur que vous pouvez écrire une expression régulière qui accepte tous les palindromes plus petits qu’une certaine longueur fixe. S’il existe une application du monde réel qui nécessite l’identification de palindromes, elle n’inclut presque certainement pas les longues, donc cette réponse montrerait que vous pouvez différencier les impossibilités théoriques des applications réelles. Cependant, l’expression rationnelle réelle serait assez longue, beaucoup plus longue qu’un programme équivalent à 4 lignes (exercice facile pour le lecteur: rédiger un programme qui identifie les palindromes).

Bien que le moteur PCRE prenne en charge les expressions régulières récursives (voir la réponse de Peter Krauss ), vous ne pouvez pas utiliser une expression régulière sur le moteur ICU (utilisé par exemple par Apple) pour y parvenir sans code supplémentaire. Vous devrez faire quelque chose comme ceci:

Cela détecte tout palindrome, mais nécessite une boucle (qui sera nécessaire car les expressions régulières ne peuvent pas compter).

 $a = "testssortingng"; while(length $a > 1) { $a =~ /(.)(.*)(.)/; die "Not a palindrome: $a" unless $1 eq $3; $a = $2; } print "Palindrome"; 

Ce n’est pas possible. Les palindromes ne sont pas définis par un langage régulier. (Voir, j’ai appris quelque chose en théorie informatique)

Avec Perl regex:

 /^((.)(?1)\2|.?)$/ 

Bien que, comme beaucoup l’ont souligné, cela ne peut être considéré comme une expression régulière si vous voulez être ssortingct. Les expressions régulières ne prennent pas en charge la récursivité.

En voici un pour détecter les palindromes à 4 lettres (ex: acte), pour tout type de personnage:

 \(.\)\(.\)\2\1 

En voici un pour détecter les palindromes à 5 lettres (ex: radar), en vérifiant uniquement les lettres:

 \([az]\)\([az]\)[az]\2\1 

Il semble donc que nous ayons besoin d’une expression rationnelle différente pour chaque longueur de mot possible. Cet article sur une liste de diffusion Python contient des détails sur les raisons (automates à états finis et lemme de pompage).

Oui , vous pouvez le faire dans .Net!

 (?.)+.?(?< -N>\k)+(?(N)(?!)) 

Vous pouvez le vérifier ici ! C’est un article merveilleux!

Selon votre confiance, je donnerais cette réponse:

Je ne le ferais pas avec une expression régulière. Ce n’est pas une utilisation appropriée des expressions régulières.

Comme certains l’ont déjà dit, il n’existe aucune expression rationnelle qui détecte un palindrome général, mais si vous souhaitez détecter des palindromes d’une certaine longueur, vous pouvez utiliser quelque chose comme:

 (.?)(.?)(.?)(.?)(.?).?\5\4\3\2\1 

StackOverflow est plein de réponses comme “Expressions régulières? Non, ils ne le supportent pas. Ils ne peuvent pas le supporter”.

La vérité est que les expressions régulières n’ont plus rien à voir avec les grammaires régulières . Les expressions régulières modernes comportent des fonctions telles que les groupes de récursivité et d’équilibrage, et la disponibilité de leurs implémentations ne cesse de croître (voir les exemples Ruby ici, par exemple). À mon avis, la croyance ancienne selon laquelle les expressions régulières dans notre domaine sont tout sauf un concept de programmation est tout simplement contre-productif. Au lieu de les haïr pour le choix du mot qui n’est plus le plus approprié, il est temps pour nous d’accepter les choses et d’aller de l’avant.

Voici une citation de Larry Wall , le créateur de Perl lui-même:

(…) Généralement lié à ce que nous appelons des «expressions régulières», qui ne sont que marginalement liées à des expressions régulières réelles. Néanmoins, le terme a augmenté avec les capacités de nos moteurs de correspondance de modèles, donc je ne vais pas essayer de lutter contre la nécessité linguistique ici. Je les appellerai cependant généralement «regexes» (ou «regexen», quand je suis d’humeur anglo-saxonne).

Et voici un article de blog de l’ un des principaux développeurs de PHP :

Comme l’article était assez long, voici un résumé des principaux points:

  • Les «expressions régulières» utilisées par les programmeurs ont très peu en commun avec la notion originale de régularité dans le contexte de la théorie du langage formel.
  • Les expressions régulières (au moins PCRE) peuvent correspondre à tous les langages sans contexte. En tant que tels, ils peuvent également correspondre à du HTML bien formé et à peu près tous les autres langages de programmation.
  • Les expressions régulières peuvent correspondre à au moins certaines langues sensibles au contexte.
  • La correspondance des expressions régulières est NP-complet. En tant que tel, vous pouvez résoudre tout autre problème NP en utilisant des expressions régulières.

Cela dit, vous pouvez faire correspondre les palindromes avec les regexes en utilisant ceci:

 ^(?'letter'[az])+[az]?(?:\k'letter'(?'-letter'))+(?(letter)(?!))$ 

… ce qui n’a évidemment rien à voir avec les grammaires régulières.
Plus d’infos ici: http://www.regular-expressions.info/balancing.html

En ruby, vous pouvez utiliser des groupes de capture nommés. alors quelque chose comme ça fonctionnera –

 def palindrome?(ssortingng) $1 if ssortingng =~ /\A(?

| \w | (?: (?\w) \g

\k ))\z/x end

Essayez, ça marche …

 1.9.2p290 :017 > palindrome?("racecar") => "racecar" 1.9.2p290 :018 > palindrome?("kayak") => "kayak" 1.9.2p290 :019 > palindrome?("woahitworks!") => nil 

Cela peut être fait en Perl maintenant. En utilisant une référence récursive:

 if($istr =~ /^((\w)(?1)\g{-1}|\w?)$/){ print $istr," is palindrome\n"; } 

modifié sur la base de la dernière partie http://perldoc.perl.org/perlretut.html

 /\A(?|.|(?:(?.)\g\k))\z/ 

il est valable pour le moteur Oniguruma (utilisé dans Ruby)

pris de Pragmatic Bookshelf

Il est en fait plus facile de le faire avec la manipulation de chaînes plutôt qu’avec des expressions régulières:

 bool isPalindrome(Ssortingng s1) { Ssortingng s2 = s1.reverse; return s2 == s1; } 

Je me rends compte que cela ne répond pas vraiment à la question de l’interview, mais vous pouvez l’utiliser pour montrer comment vous connaissez une meilleure façon de faire une tâche, et vous n’êtes pas la personne habituelle qui voit chaque problème comme un clou. . ”

En Perl (voir aussi la réponse de Zsolt Botykai ):

 $re = qr/ . # single letter is a palindrome | (.) # first letter (??{ $re })?? # apply recursivly (not interpolated yet) \1 # last letter /x; while(<>) { chomp; say if /^$re$/; # print palindromes } 

Concernant l’expression PCRE (de MizardX):

/^((.)(?1)\2|.?)$/

L’avez-vous testé? Sur mon PHP 5.3 sous Win XP Pro, il échoue sur: aaaba En fait, j’ai légèrement modifié l’expression, pour lire:

/^((.)(?1)*\2|.?)$/

Je pense que ce qui se passe est que tandis que la paire de caractères extérieure est ancrée, les autres ne le sont pas. Ce n’est pas tout à fait la réponse car, bien qu’elle ne soit pas correctement transmise “aaaba” et “aabaacaa”, elle échoue correctement sur “aabaaca”.

Je me demande s’il existe un correctif pour cela, et aussi, l’exemple Perl (par JF Sebastian / Zsolt) passe-t-il correctement mes tests?

Csaba Gabor de Vienne

Voici ma réponse au 5ème niveau de Regex Golf (Un homme, un plan). Il fonctionne avec jusqu’à 7 caractères avec le Regexp du navigateur (j’utilise Chrome 36.0.1985.143).

 ^(.)(.)(?:(.).?\3?)?\2\1$ 

En voici un pour 9 caractères maximum

 ^(.)(.)(?:(.)(?:(.).?\4?)?\3?)?\2\1$ 

Pour augmenter le nombre maximum de caractères, cela remplacerait à plusieurs resockets .? avec (?: (.).? \ n?)? .

Comme ZCHudson l’a souligné , déterminer si quelque chose est un palindrome ne peut pas être fait avec une expression rationnelle habituelle, car l’ensemble des palindromes n’est pas un langage normal.

Je ne suis pas du tout d’accord avec Airsource Ltd lorsqu’il dit que “c’est pas possible” n’est pas le genre de réponse que l’interviewer recherche. Lors de mon entretien, j’arrive à ce genre de question lorsque je suis confronté à un bon candidat, pour vérifier s’il peut trouver le bon argument lorsque nous lui avons proposé de faire quelque chose de mal. Je ne veux pas embaucher quelqu’un qui essaiera de faire quelque chose dans le mauvais sens s’il en connaît un meilleur.

quelque chose que vous pouvez faire avec perl: http://www.perlmonks.org/?node_id=577368

J’expliquerais à l’intervieweur que la langue constituée par les palindromes n’est pas une langue normale mais plutôt dépourvue de contexte.

L’expression régulière qui correspondrait à tous les palindromes serait infinie . Au lieu de cela, je suggère qu’il se limite à une taille maximale de palindromes à accepter; ou si tous les palindromes sont nécessaires, utilisez au minimum un certain type de NDPA, ou utilisez simplement la technique simple d’inversion de chaîne / d’égalité.

Le mieux que vous puissiez faire avec les expressions rationnelles, avant de manquer de groupes de capture:

 /(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?).?\9\8\7\6\5\4\3\2\1/ 

Cela correspondra à tous les palindromes de 19 caractères maximum.

La résolution programmée pour toutes les longueurs est sortingviale:

 str == str.reverse ? true : false 

Je n’ai pas encore le commentaire pour commenter en ligne, mais la regex fournie par MizardX, et modifiée par Csaba, peut être modifiée pour la faire fonctionner dans PCRE. Le seul échec que j’ai trouvé est la chaîne de caractères uniques, mais je peux tester cela séparément.

/^((.)(?1)?\2|.)$/

Si vous pouvez le faire échouer sur d’autres chaînes, veuillez commenter.

 #!/usr/bin/perl use ssortingct; use warnings; print "Enter your ssortingng: "; chop(my $a = scalar()); my $m = (length($a)+1)/2; if( (length($a) % 2 != 0 ) or length($a) > 1 ) { my $r; foreach (0 ..($m - 2)){ $r .= "(.)"; } $r .= ".?"; foreach ( my $i = ($m-1); $i > 0; $i-- ) { $r .= "\\$i"; } if ( $a =~ /(.)(.).\2\1/ ){ print "$a is a palindrome\n"; } else { print "$a not a palindrome\n"; } exit(1); } print "$a not a palindrome\n"; 

De la théorie des automates, il est impossible de faire correspondre un paliandrome de toute longueur (car cela nécessite une quantité de mémoire infinie). Mais il est possible de faire correspondre les paliandromes de longueur fixe. Disons qu’il est possible d’écrire une expression rationnelle qui correspond à tous les paliandromes de longueur < = 5 ou <= 6, etc., mais pas> = 5, etc.

Dans Ruby, vous pouvez utiliser \b(?'word'(?'letter'[az])\g'word'\k'letter+0'|[az])\b pour correspondre à des mots palindrome tels que a, dad, radar, racecar, and redivider . ps: cette regex ne correspond qu’à des mots palindromes d’un nombre impair de lettres.

Voyons comment cette regex correspond au radar. Le mot boundary \ b correspond au début de la chaîne. Le moteur d’expressions rationnelles entre dans le groupe de saisie “mot”. [az] correspond à r qui est ensuite stocké dans la stack pour le groupe de saisie “lettre” au niveau de récursivité zéro. Maintenant, le moteur d’expression régulière entre la première récursivité du groupe “mot”. (? ‘lettre’ [az]) correspond et capture un niveau de récursivité. La regex entre dans la deuxième récursivité du groupe “mot”. (? ‘lettre’ [az]) capture d au niveau de récursivité deux. Au cours des deux prochaines récurrences, le groupe capture a et r aux niveaux trois et quatre. La cinquième récursivité échoue car il ne rest aucun caractère dans la chaîne pour que [az] corresponde. Le moteur regex doit faire marche arrière.

Le moteur d’expressions rationnelles doit maintenant essayer la deuxième alternative dans le groupe “mot”. Le second [az] dans l’expression régulière correspond au dernier r de la chaîne. Le moteur sort maintenant d’une récursivité réussie, remontant d’un niveau à la troisième récursivité.

Après correspondance (& word), le moteur atteint \ k’letter + 0 ‘. La référence arrière échoue car le moteur de regex a déjà atteint la fin de la chaîne de sujet. Donc, il fait un retour en arrière une fois de plus. La deuxième alternative correspond maintenant à la. Le moteur regex quitte la troisième récursivité.

Le moteur d’expressions rationnelles a de nouveau été associé (& word) et doit à nouveau tenter la référence arrière. La référence arrière spécifie +0 ou le niveau actuel de la récursivité, qui est 2. À ce niveau, le groupe de capture correspond à d. La référence arrière échoue car le caractère suivant de la chaîne est r. Revenons en arrière, la deuxième alternative correspond à d.

Maintenant, \ k’letter + 0 ‘correspond à la seconde a de la chaîne. C’est parce que le moteur regex est arrivé à la première récursivité pendant laquelle le groupe de capture correspondait au premier a. Le moteur d’expressions rationnelles quitte la première récursivité.

Le moteur regex est maintenant de retour en dehors de toute récursivité. Que ce niveau, le groupe de capture stocké r. Le backreference peut maintenant correspondre au dernier r de la chaîne. Comme le moteur n’est plus dans une récursivité, il continue avec le rest de l’expression régulière après le groupe. \ b correspond à la fin de la chaîne. La fin de l’expression rationnelle est atteinte et le radar est renvoyé comme match global.

Voici le code PL / SQL qui indique si une chaîne donnée est palindrome ou n’utilise pas les expressions régulières:

 create or replace procedure palin_test(palin in varchar2) is tmp varchar2(100); i number := 0; BEGIN tmp := palin; for i in 1 .. length(palin)/2 loop if length(tmp) > 1 then if regexp_like(tmp,'^(^.).*(\1)$') = true then tmp := substr(palin,i+1,length(tmp)-2); else dbms_output.put_line('not a palindrome'); exit; end if; end if; if i >= length(palin)/2 then dbms_output.put_line('Yes ! it is a palindrome'); end if; end loop; end palin_test; 

Les expressions régulières récursives peuvent le faire!

Un algorithme si simple et évident pour détecter une chaîne contenant un palindrome:

  (\w)(?:(?R)|\w?)\1 

Sur rexegg.com/regex-recursion, le tutoriel explique comment cela fonctionne.


Cela fonctionne très bien avec n’importe quel langage, ici un exemple adapté de la même source (lien) que la preuve de concept, en utilisant PHP:

 $subjects=['dont','o','oo','kook','book','paper','kayak','okonoko','aaaaa','bbbb']; $pattern='/(\w)(?:(?R)|\w?)\1/'; foreach ($subjects as $sub) { echo $sub." ".str_repeat('-',15-strlen($sub))."-> "; if (preg_match($pattern,$sub,$m)) echo $m[0].(($m[0]==$sub)? "! a palindrome!\n": "\n"); else echo "sorry, no match\n"; } 

les sorties

 dont ------------> sorry, no match o ---------------> sorry, no match oo --------------> oo! a palindrome! kook ------------> kook! a palindrome! book ------------> oo paper -----------> pap kayak -----------> kayak! a palindrome! okonoko ---------> okonoko! a palindrome! aaaaa -----------> aaaaa! a palindrome! bbbb ------------> bbb 

Comparant

L’expression régulière ^((\w)(?:(?1)|\w?)\2)$ fait le même travail, mais à la place oui / non “contient”.
PS: il utilise une définition où “o” n’est pas un palimbrome, le format hyphened “able-elba” n’est pas un palindrome, mais “ableelba” l’est. Nommez-le definition1 .
Quand “o” et “able-elba” sont des palindrones, nommer definition2 .

En comparant avec un autre “regexes palindrome”,

  • ^((.)(?:(?1)|.?)\2)$ base-regex ci-dessus sans ressortingction \w , acceptant “able-elba”.

  • ^((.)(?1)?\2|.)$ ( @LilDevil ) Utilise la définition2 (accepte “o” et “able-elba” si différent aussi dans la reconnaissance des chaînes “aaaaa” et “bbbb”).

  • ^((.)(?1)\2|.?)$ ( @Markus ) non détecté “kook” ni “bbbb”

  • ^((.)(?1)*\2|.?)$ ( @Csaba ) Utilise la définition2 .


NOTE: pour comparer, vous pouvez append plus de mots à $subjects et une ligne pour chaque regex comparée,

  if (preg_match('/^((.)(?:(?1)|.?)\2)$/',$sub)) echo " ...reg_base($sub)!\n"; if (preg_match('/^((.)(?1)?\2|.)$/',$sub)) echo " ...reg2($sub)!\n"; if (preg_match('/^((.)(?1)\2|.?)$/',$sub)) echo " ...reg3($sub)!\n"; if (preg_match('/^((.)(?1)*\2|.?)$/',$sub)) echo " ...reg4($sub)!\n"; 

Un léger raffinement de la méthode d’Airsource Ltd, en pseudocode:

 WHILE ssortingng.length > 1 IF /(.)(.*)\1/ matches ssortingng ssortingng = \2 ELSE REJECT ACCEPT 

Vous pouvez aussi le faire sans utiliser la récursivité:

 \A(?:(.)(?=.*?(\1\2?)\z))*?.?\2\z 

ou pour exclure la chaîne vide:

 \A(?=.)(?:(.)(?=.*?(\1\2?)\z))*?.?\2\z 

Fonctionne avec Perl, PCRE, Ruby, Java

démo

mon $ pal = ‘malayalam’;

 while($pal=~/((.)(.*)\2)/){ #checking palindrome word $pal=$3; } if ($pal=~/^.?$/i){ #matches single letter or no letter print"palindrome\n"; } else{ print"not palindrome\n"; } 

\b([az])?([az])?([az])?\2\1\b/gi

Correspond à 5 palindromes tels que refer et kayak. Pour ce faire, il utilise une correspondance (non gourmande) de trois lettres, suivie des deuxième et deuxième lettres correspondantes.

Lien vers le site regex101 en utilisant ceci