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

Question

C’est une question de l’entrevue à laquelle j’ai été incapable de répondre:

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

p.s. Il y a déjà une question & Quot; Comment vérifier si la chaîne donnée est palindrome? " et il donne beaucoup de réponses dans différentes langues, mais pas de réponse utilisant des expressions régulières.

Answer 1

La réponse à cette question est que & "c'est impossible &". Plus spécifiquement, 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 découvert les machines à états finis. Une machine à états finis est composée de nœuds et d'arêtes. Chaque arête est annotée avec une lettre d'un alphabet fini. Un ou plusieurs nœuds sont spéciaux & "Accepter" & "; Les nœuds et un nœud est le " start " nœud. Lorsque chaque lettre est lue à partir d'un mot donné, nous traversons le bord donné dans la machine. Si nous nous retrouvons dans un état d'acceptation, nous dirons que la machine & "Accepte &"; ce mot.

Une expression régulière peut toujours être traduite en 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'expressions rationnelles autorisent des fonctions arbitraires, celles-ci ne comptent pas).

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

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

où a ^ x est répété 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 bien 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 plus petits que certaines longueurs fixes finies. S'il existe une application du monde réel nécessitant l'identification de palindromes, elle n'inclura presque certainement pas les longues longueurs arbitraires. Cette réponse montrerait donc que vous pouvez différencier les impossibilités théoriques des applications du monde réel. Néanmoins, l’expression rationnelle réelle serait assez longue, bien plus longue qu’un programme équivalent de 4 lignes (exercice simple pour le lecteur: écrivez un programme identifiant les palindromes).

Answer 2

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 ICU (utilisé par exemple par Apple) pour y parvenir sans code supplémentaire. Vous devrez faire quelque chose comme ça:

Ceci détecte tout palindrome, mais nécessite une boucle (ce 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";

Answer 3

Ce n'est pas possible. Les palindromes ne sont pas définis par un langage ordinaire. (Voir, j'ai appris quelque chose dans la théorie informatique)

Answer 4

Avec l'expression rationnelle Perl:

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

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

Answer 5

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

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

En voici un pour détecter les palindromes à 5 lettres (par exemple: radar ), vérification des lettres uniquement:

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

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

Answer 6

En fonction de votre confiance, je donnerais cette réponse:

  

Je ne le ferais pas avec un habitué   expression. Ce n'est pas un approprié   utilisation d'expressions régulières.

Answer 7

Oui , vous pouvez le faire en .Net!

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

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

Answer 8

Comme certains l’ont déjà dit, il n’existe pas d’expression rationnelle unique 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

Answer 9

StackOverflow regorge de réponses telles que & "; Expressions régulières? Nope, ils ne le supportent pas. Ils ne peuvent pas le soutenir. & ";

La vérité est que les expressions rationnelles n'ont plus rien à voir avec les grammaires régulières . Les expressions régulières modernes présentent des fonctions telles que la récursion et l'équilibrage des groupes, ainsi que la disponibilité de leurs implémentations. est en croissance constante (voir les exemples Ruby ici, par exemple). À mon avis, rester accroché à 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 que nous acceptions les choses et passions à autre chose.

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

  

(& # 8230;) concerne généralement ce que nous appelons & # 8220; expressions rationnelles & # 8221 ;, qui ne sont que marginalement liées à de vraies expressions régulières. Néanmoins, le terme a évolué avec les capacités de nos moteurs de filtrage, donc je & # 8217; je ne vais pas essayer de lutter contre la nécessité linguistique ici. Cependant, je les appellerai généralement & # 8220; regexes & # 8221; (ou & # 8220; regexen & # 8221 ;, quand je & # 8217; suis d'humeur anglo-saxonne).

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

  

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

     

  
• Les & # 8220; expressions régulières & # 8221; utilisés par les programmeurs ont très peu en commun avec la notion originale de régularité dans le contexte de la théorie des langages formels.
  
• Les expressions régulières (au moins PCRE) peuvent correspondre à tous les langages sans contexte. En tant que tels, ils peuvent également correspondre à du code HTML bien formé et à presque tous les autres langages de programmation.
  
• Les expressions régulières peuvent correspondre à au moins certains langages sensibles au contexte.
  
• La 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 les palindromes avec des regex en utilisant ceci:

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

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

Answer 10

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

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

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

Answer 11

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

def palindrome?(string)
  $1 if string =~ /\A(?<p>| \w | (?: (?<l>\w) \g<p> \k<l+0> ))\z/x
end

l'essayer, ça marche ...

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

Answer 12

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

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

En voici un qui peut contenir jusqu'à 9 caractères

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

Pour augmenter le nombre maximal de caractères pour lesquels il fonctionnerait, vous devez remplacer à plusieurs reprises .? par (?: (.).? \ n?)? .

Answer 13

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

valable pour le moteur Oniguruma (utilisé en Ruby)

extrait de une bibliothèque pragmatique

.

Answer 14

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

bool isPalindrome(String s1)

{

    String s2 = s1.reverse;

    return s2 == s1;
}

Je réalise que cela ne répond pas vraiment à la question de l'entrevue, 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. & ";

Answer 15

En Perl (voir aussi 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
}

Answer 16

En ce qui concerne 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, comme suit:

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

Je pense que ce qui se passe est que, si la paire de caractères externe est ancrée, les autres ne le sont pas. Ce n’est pas tout à fait la réponse car, même s’il transmet incorrectement & «Aaaba &»; et & "aabaacaa &"; il échoue correctement sur & "aabaaca &";.

Je me demande s'il existe une solution pour cela, et aussi, L’exemple Perl (de JF Sebastian / Zsolt) réussit-il correctement mes tests?

Csaba Gabor de Vienne

Answer 17

Les expressions rationnelles récursives peuvent le faire!

Algorithme si simple et évident pour détecter une chaîne qui contient un palindrome:

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

Dans le rexegg.com/regex-recursion , le didacticiel explique son fonctionnement.

Cela fonctionne très bien avec n'importe quel langage, voici un exemple adapté de la même source (lien) comme 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";
}

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

Comparaison

L'expression régulière ^((\w)(?:(?1)|\w?)\2)$ effectue le même travail, mais comme oui / pas à la place & "; contient &";
PS: il utilise une définition où " o " n'est pas un palimbrome, & "capable-elba &"; Le format avec un trait d'union n'est pas un palindrome, mais & "capableelba &"; est. Le nommer definition1 .
Quand " o " et " capable-elba " sont des palindrones, nommant definition2 .

Comparaison avec d'autres & "; expressions rationnelles palindromes &",

• ^((.)(?:(?1)|.?)\2)$ la regex de base ci-dessus sans \w restriction, en acceptant & "capable-elba &";.

• ^((.)(?1)?\2|.)$ ( @LilDevil ) Utilisez definition2 (accepte " ; o & "et &" capable-elba & "aussi différent dans la reconnaissance de &" aaaaa & "et &" bbbb & " ; strings).

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

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

NOTE: pour comparer, vous pouvez ajouter plus de mots à $subjects et une ligne pour chaque expression rationnelle 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";

Answer 18

Comme indiqué par ZCHudson , déterminez si quelque chose est un palindrome ne peut pas être fait avec une expression rationnelle habituelle, car l'ensemble de palindrome n'est pas une langue normale.

Je suis totalement en désaccord avec Airsource Ltd quand il dit que & "Ce n'est pas possible &"; Ce n'est pas le genre de réponse que l'intervieweur recherche. Au cours de mon entretien, j’arrive à ce genre de question lorsque j’affronte un bon candidat afin de 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 mieux.

Answer 19

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

Answer 20

Je voudrais expliquer à l'intervieweur que le langage composé de palindromes n'est pas un langage courant, mais qu'il est dépourvu de contexte.

L’expression régulière qui correspondrait à tous les palindromes serait infini . Au lieu de cela, je lui suggérerais de se limiter soit à accepter une taille maximale de palindromes; ou si tous les palindromes sont nécessaires, utilisez au minimum un type de NDPA, ou utilisez simplement la technique simple inversion de chaîne / égal à.

Answer 21

Le mieux que vous puissiez faire avec les regex avant de manquer de groupes de capture:

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

Ceci correspond à tous les palindromes de 19 caractères maximum.

La résolution par programme pour toutes les longueurs est simple:

str == str.reverse ? true : false

Answer 22

Je n'ai pas encore le représentant en commentaire en ligne, mais l'expression régulière fournie par MizardX, et modifiée par Csaba, peut être modifiée davantage pour le rendre fonctionnel dans PCRE. Le seul échec que j'ai trouvé est la chaîne à un seul caractère, mais je peux le tester séparément.

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

Si vous pouvez faire échouer d'autres chaînes, veuillez commenter.

Answer 23

#!/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";

Answer 24

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. Dites qu'il est possible d'écrire une expression rationnelle qui corresponde à tous les paliandromes de longueur & Lt; = 5 ou & Lt; = 6 etc., mais pas & Gt; = 5 etc. où la borne supérieure n'est pas claire

Answer 25

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

Voyons comment cette regex correspond au radar. La limite de mot \ b correspond au début de la chaîne. Le moteur des expressions rationnelles entre dans le groupe de capture & "; Mot &"; [a-z] correspond à r qui est ensuite stocké dans la pile du groupe de capture " lettre " au niveau de récurrence zéro. Maintenant, le moteur de regex entre la première récurrence du groupe & "Mot &"; (? 'lettre' [a-z]) correspond et capture un niveau de récursivité un. La regex entre dans la deuxième récurrence du groupe & "Mot &"; (? 'lettre' [a-z]) capture d au niveau de récurrence deux. Au cours des deux prochaines récurrences, le groupe capture a et r aux niveaux trois et quatre. La cinquième récursion échoue car il ne reste plus de caractères dans la chaîne que [a-z] puisse faire correspondre. Le moteur de regex doit revenir en arrière.

Le moteur des expressions rationnelles doit maintenant essayer la deuxième alternative du groupe & "mot &"; Le second [a-z] de la regex correspond au dernier r de la chaîne. Le moteur sort maintenant d’une récursivité réussie, remontant d’un niveau jusqu’à la troisième récursivité.

Après avoir mis en correspondance (& amp; word), le moteur atteint \ k'letter + 0 '. La référence arrière échoue car le moteur des expressions rationnelles a déjà atteint la fin de la chaîne de sujet. Donc, il revient une fois de plus. La deuxième alternative correspond maintenant à la a. Le moteur de regex sort de la troisième récursivité.

Le moteur des expressions rationnelles a de nouveau correspondu (& amp; word) et doit essayer à 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 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. De nouveau en arrière, la deuxième alternative correspond à d.

Maintenant, \ k'letter + 0 'correspond au second a de la chaîne. En effet, le moteur des expressions rationnelles est revenu à la première récursivité au cours de laquelle le groupe de capture correspondait à la première a. Le moteur de regex quitte la première récursivité.

Le moteur de regex est maintenant de retour en dehors de toute récursion. Que ce niveau, le groupe de capture stocké r. La référence arrière peut maintenant correspondre au dernier r de la chaîne. Comme le moteur n’est plus dans aucune récursion, il continue avec le reste de la regex après le groupe. \ b correspond à la fin de la chaîne. La fin de la regex est atteinte et le radar est renvoyé sous forme de match.

Answer 26

Voici le code PL / SQL qui indique si une chaîne donnée est palindrome ou non à l'aide d'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;

Answer 27

Vous pouvez également 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

Answer 28

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

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

Answer 29

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

Answer 30

\b([a-z])?([a-z])?([a-z])?\2\1\b/gi

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

Lien vers le site regex101 à l'aide de ce lien