Comment vérifier qu'une chaîne est un palindrome à l'aide d'expressions régulières?

C'était une question d'entrevue à laquelle je n'ai pas pu répondre:

Comment vérifier qu'une chaîne est un palindrome à l'aide d'expressions régulières?

ps Il y a déjà une question " Comment vérifier si la chaîne donnée est palindrome? " et elle donne beaucoup de réponses dans différentes langues, mais aucune 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 prêté attention à votre cours de théorie computationnelle.

Dans votre cours de théorie computationnelle, vous avez appris les machines à états finis. Une machine à états finis est composée de nœuds et d'arêtes. Chaque bord est annoté d'une lettre d'un alphabet fini. Un ou plusieurs nœuds sont des nœuds spéciaux "accepteurs" et un nœud est le nœud "de départ". Comme chaque lettre est lue à partir d'un mot donné, nous traversons l'arête donnée dans la machine. Si nous nous retrouvons dans un état d'acceptation, nous disons que la machine «accepte» ce mot.

Une expression régulière peut toujours être traduite en une machine à états finis équivalente. Autrement dit, celui qui accepte et rejette les mêmes mots que l'expression régulière (dans le monde réel, certains langages d'expression régulière 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 s'appuie sur les faits que l'on peut facilement construire une chaîne qui nécessite 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 pouvez dire à l'intervieweur que vous pouvez écrire une expression régulière qui accepte tous les palindromes qui sont plus petits qu'une longueur fixe finie. S'il y a jamais une application dans le monde réel qui nécessite l'identification de palindromes, alors elle n'inclura presque certainement pas de palindromes arbitrairement longs, ainsi cette réponse montrerait que vous pouvez différencier les impossibilités théoriques des applications du monde réel. Pourtant, l'expression rationnelle réelle serait assez longue, beaucoup plus longue qu'un programme équivalent à 4 lignes (exercice facile pour le lecteur: écrire un programme qui identifie les palindromes).

Alors que le moteur PCRE prend 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 (tel qu'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 = "teststring";
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 computationnelle)

Avec Perl regex:

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

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

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

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

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

\([a-z]\)\([a-z]\)[a-z]\2\1

Il semble donc que nous ayons besoin d'une expression régulière différente pour chaque longueur de mot possible. Cet article sur une liste de diffusion Python comprend quelques détails sur les raisons (Automates à états finis et lemme de pompage).

En fonction de votre confiance en vous, 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.

Oui , vous pouvez le faire dans .Net!

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

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

StackOverflow est plein de réponses comme "Les expressions régulières? Non, elles 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 la récursivité et les groupes d'équilibrage, et la disponibilité de leurs implémentations ne cesse de croître (voir les exemples Ruby ici, par exemple). À mon avis, s'accrocher à la vieille croyance 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 de mots qui n'est plus le plus approprié, il est temps pour nous d'accepter les choses et de passer à autre chose.

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

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

Et voici un article de blog rédigé par l' un des principaux développeurs 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 de points communs 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 à presque tous les autres langages de programmation.
• Les expressions régulières peuvent correspondre à au moins certains langages contextuels.
• La mise en correspondance des expressions régulières est NP-complète. En tant que tel, vous pouvez résoudre tout autre problème NP en utilisant des expressions régulières.

Cela étant dit, vous pouvez faire correspondre des palindromes avec des regex en utilisant ceci:

^(?'letter'[a-z])+[a-z]?(?:\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

Comme certains l'ont déjà dit, il n'y a pas une seule expression rationnelle qui détecte un palindrome général hors de la boîte, mais si vous voulez détecter des palindromes jusqu'à une certaine longueur, vous pouvez utiliser quelque chose comme

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

Cela peut être fait en Perl maintenant. Utilisation d'une référence récursive:

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

modifié en fonction de la presque dernière partie http://perldoc.perl.org/perlretut.html

Dans ruby, vous pouvez utiliser des groupes de capture nommés. donc quelque chose comme ça fonctionnera -

def palindrome?(string)
  $1 if string =~ /\A(?<p>| \w | (?: (?<l>\w) \g<p> \k<l+0> ))\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 

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

bool isPalindrome(String s1)

{

    String s2 = s1.reverse;

    return s2 == s1;
}

Je me rends compte que cela ne répond pas vraiment à la question de l'entretien, 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 typique avec un marteau, qui voit chaque problème comme un clou . "

Voici ma réponse au 5ème niveau de Regex Golf (Un homme, un plan). Cela fonctionne 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 pour lesquels il fonctionnerait, vous remplaceriez à plusieurs reprises .? avec (?: (.).? \ n?)? .

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

Algorithme tellement 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 bien avec n'importe quel langage, voici 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 comme oui / non à la place "contient".
PS: il utilise une définition où "o" n'est pas un palimbrome, le format avec tiret "able-elba" n'est pas un palindrome, mais "ableelba" l'est. Nommer sa définition 1 .
Quand "o" et "able-elba" sont des palindrones, nommer definition2 .

Comparaison avec une autre "regexe palindrome",

• ^((.)(?:(?1)|.?)\2)$la base-regex ci-dessus sans \wrestriction, acceptant "capable-elba".

• ^((.)(?1)?\2|.)$( @LilDevil ) Utilise definition2 (accepte "o" et "able-elba" donc différant aussi dans la reconnaissance des chaînes "aaaaa" et "bbbb").

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

• ^((.)(?1)*\2|.?)$( @Csaba ) Utilisez definition2 .

REMARQUE: pour comparer, vous pouvez ajouter plus de mots à $subjectset une ligne pour chaque expression régulière 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";

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

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

pour autoriser un seul caractère:

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

Fonctionne avec Perl, PCRE

démo

Pour Java:

\A(?:(.)(?=.*?(\1\2\z|(?<!(?=\2\z).{0,1000})\1\z)))*?.?\2\z

démo

Concernant l'expression PCRE (de MizardX):

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

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

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

Je pense que ce qui se passe, c'est que si la paire externe de caractères est ancrée, les autres internes ne le sont pas. Ce n'est pas tout à fait la réponse car si elle transmet incorrectement "aaaba" et "aabaacaa", elle échoue correctement sur "aabaaca".

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

Csaba Gabor de Vienne

/\A(?<a>|.|(?:(?<b>.)\g<a>\k<b+0>))\z/

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

tiré de Pragmatic Bookshelf

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
}

Comme l'a souligné ZCHudson , déterminer si quelque chose est un palindrome ne peut pas être fait avec une expression régulière habituelle, car l'ensemble de palindrome n'est pas un langage régulier.

Je suis totalement en désaccord avec Airsource Ltd quand il dit que "ce n'est pas possible" n'est pas le genre de réponse que l'intervieweur recherche. Lors de mon entretien, j'arrive à ce genre de question lorsque je fais face à un bon candidat, pour vérifier s'il peut trouver le bon argument quand on lui propose de faire quelque chose de mal. Je ne veux pas embaucher quelqu'un qui essaiera de faire quelque chose de mal s'il en connaît une meilleure.

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

J'expliquerais à l'intervieweur que la langue constituée de palindromes n'est pas une langue ordinaire mais plutôt sans contexte.

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

Le mieux que vous puissiez faire avec les expressions régulières, avant de manquer de groupes de capture:

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

Cela correspondra à tous les palindromes jusqu'à 19 caractères de longueur.

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

str == str.reverse ? true : false

Je n'ai pas encore le représentant pour commenter en ligne, mais le regex fourni par MizardX, et modifié par Csaba, peut être modifié davantage pour le faire fonctionner dans PCRE. Le seul échec que j'ai trouvé est la chaîne à caractère unique, 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 strict;
use warnings;

print "Enter your string: ";
chop(my $a = scalar(<STDIN>));    
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é infinie de mémoire). Mais IL EST POSSIBLE de faire correspondre des paliandromes de longueur fixe. Dites qu'il est possible d'écrire une expression régulière qui correspond à tous les paliandromes de longueur <= 5 ou <= 6 etc, mais pas> = 5 etc où la limite supérieure n'est pas claire

Dans Ruby, vous pouvez utiliser \b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z])\bpour faire correspondre des mots palindrome tels que a, dad, radar, racecar, and redivider. ps: cette expression rationnelle ne correspond qu'aux mots palindromes d'un nombre impair de lettres.

Voyons comment cette expression régulière correspond au radar. Le mot limite \ b correspond au début de la chaîne. Le moteur regex entre dans le groupe de capture "mot". [az] correspond à r qui est ensuite stocké dans la pile pour le groupe de capture "lettre" au niveau de récursivité zéro. Maintenant, le moteur regex entre dans la première récursion du groupe "mot". (? 'letter' [az]) correspond et capture un au niveau de récursivité un. Le regex entre dans la deuxième récursion du groupe "mot". (? 'letter' [az]) capture d au niveau de récursivité deux. Au cours des deux récursions suivantes, le groupe capture a et r aux niveaux trois et quatre. La cinquième récursivité échoue car il ne reste aucun caractère dans la chaîne pour que [az] corresponde. Le moteur regex doit revenir en arrière.

Le moteur regex doit maintenant essayer la deuxième alternative à l'intérieur du groupe "mot". Le deuxième [az] de l'expression régulière correspond au r final de la chaîne. Le moteur sort maintenant d'une récursion réussie, remontant d'un niveau à la troisième récursivité.

Après avoir mis en correspondance (& mot), le moteur atteint \ k'letter + 0 '. La backreference échoue car le moteur regex a déjà atteint la fin de la chaîne de sujet. Donc, il revient en arrière. La deuxième alternative correspond maintenant au a. Le moteur regex sort de la troisième récursivité.

Le moteur regex a de nouveau correspondu (& word) et doit tenter à nouveau la référence arrière. La référence arrière spécifie +0 ou le niveau actuel de récursivité, qui est de 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. Revenir en arrière, la deuxième alternative correspond à d.

Maintenant, \ k'letter + 0 'correspond au second a de la chaîne. C'est parce que le moteur regex est revenu à la première récursion au cours de laquelle le groupe de capture correspondait au premier a. Le moteur regex 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. La référence arrière peut maintenant correspondre au r final de la chaîne. Puisque le moteur n'est plus à l'intérieur d'une récursion, il procède avec le reste de l'expression régulière après le groupe. \ b correspond à la fin de la chaîne. La fin de l'expression régulière est atteinte et le radar est renvoyé comme correspondance globale.

voici le code PL / SQL qui indique si la chaîne donnée est palindrome ou non en utilisant des 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;

my $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";
}

Cette regex détecte les palindromes jusqu'à 22 caractères en ignorant les espaces, les tabulations, les virgules et les guillemets.

\b(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*\11?[ \t,'"]*\10|\10?)[ \t,'"]*\9|\9?)[ \t,'"]*\8|\8?)[ \t,'"]*\7|\7?)[ \t,'"]*\6|\6?)[ \t,'"]*\5|\5?)[ \t,'"]*\4|\4?)[ \t,'"]*\3|\3?)[ \t,'"]*\2|\2?))?[ \t,'"]*\1\b

Jouez avec ici: https://regexr.com/4tmui

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

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