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

alors que le moteur PCRE supporte des expressions régulières récursives (voir la réponse de Peter Krauss ), vous ne pouvez pas utiliser un regex sur le moteur ICU (tel qu'utilisé, par exemple, par Apple) pour atteindre cet objectif sans code supplémentaire. Vous aurez besoin de faire quelque chose comme ceci:

cela détecte n'importe quel palindrome, mais nécessite une boucle (qui sera nécessaire parce que les expressions régulières ne peuvent pas compter).

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

c'est impossible. Les Palindromes ne sont pas définis par un langage régulier. (Voir, j'ai appris quelque chose de calcul dans la théorie)

avec Perl regex:

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

Si, comme beaucoup l'ont souligné, cela ne peut pas être considérée comme une expression régulière si vous voulez être stricte. expressions régulières ne supporte pas la récursion.

ici un pour détecter les palindromes à 4 lettres( par exemple: deed), pour tout type de caractère:

\(.\)\(.\)

ici un pour détecter les palindromes à 5 lettres( par exemple: radar), vérification pour les lettres seulement:

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

il semble donc que nous ayons besoin d'un regex différent pour chaque longueur de mot possible. ce post sur une liste de diffusion Python comprend quelques détails sur le pourquoi (état fini Automates et lemme de pompage).

Oui , vous pouvez le faire dans .Net!

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

Vous pouvez le vérifier ici ! C'est un magnifique message!

selon votre confiance, je vous répondrais:

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

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

(.?)(.?)(.?)(.?)(.?).?

StackOverflow est plein de réponses comme "expressions régulières? non, ils ne le supporte pas. Ils ne peut pas soutenir.".

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 des groupes de récursion et d'équilibrage, et la disponibilité de leurs implémentations ne cesse de croître (voir les exemples de Ruby ici, pour instance.) À mon avis, s'accrocher à la vieille croyance que les expressions régulières dans notre domaine sont tout sauf un concept de programmation est tout simplement contre-productif. Au lieu de haïr pour le choix du mot qui n'est pas le plus approprié, il est temps pour nous d'accepter les choses et d'avancer.

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

( ... ) expressions", qui ne sont que marginalement reliées aux expressions régulières réelles. Néanmoins, le terme a grandi avec les capacités de nos moteurs de correspondance de modèle, donc je ne vais pas essayer de lutter contre la nécessité linguistique ici. Je les appellerai généralement "regexes" (ou "regexen", quand je suis D'Humeur Anglo-saxonne).

et voici un post de blog par l'un des développeurs principaux 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 formelle du langage.
• les expressions régulières (au moins PCRE) peuvent correspondre à toutes les langues sans contexte. En tant que tels, ils peuvent également correspondre au HTML bien formé et à peu près tous les autres langages de programmation.
• les expressions régulières peuvent correspondre à au moins quelques langages sensibles au contexte.
• correspondance des expressions régulières est NP-complète. En tant que tel, vous pouvez résoudre n'importe quel autre problème NP en utilisant des expressions régulières.

cela dit, Vous pouvez associer les palindromes aux regexes en utilisant ceci:

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

...qui n'a évidemment rien à voir avec régulièrement des grammaires.

Plus d'informations ici: http://www.regular-expressions.info/balancing.html

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

def palindrome?(string)
   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 

cela peut être fait en Perl maintenant. En utilisant la 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 proche http://perldoc.perl.org/perlretut.html

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

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

a eu de la Pragmatique Bibliothèque

il est en fait plus facile de le faire avec la manipulation de chaîne de caractères plutôt que 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'entrevue, mais vous pourriez 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."

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

$re = qr/
  .                 # single letter is a palindrome
  |
  (.)               # first letter
  (??{ $re })??     # apply recursivly (not interpolated yet)
                  # 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 expression pour lire:

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

je pense que ce qui se passe, c'est que tandis que la paire de caractères extérieurs est ancrée, les caractères intérieurs restants ne le sont pas. Ce n'est pas tout à fait l'ensemble de la réponse parce que même si elle transmet incorrectement "aaaba" et "aabaacaa", elle échoue correctement sur "aabaaca".

je me demande s'il y a un correctif pour cela, et aussi, Est-ce que L'exemple Perl (par JF Sebastian / Zsolt) réussit mes tests correctement?

Csaba Gabor de Vienne

voici ma réponse à le 5e niveau de Regex Golf (un homme, un plan). Il fonctionne pour un maximum de 7 caractères Avec Regexp du navigateur (J'utilise Chrome 36.0.1985.143).

^(.)(.)(?:(.).??)?$

En voici un pour un maximum de 9 caractères

^(.)(.)(?:(.)(?:(.).??)??)?$

pour augmenter le nombre maximum de caractères, vous remplacez à plusieurs reprises .? avec (?: (.).?\n?)? .

les Expressions régulières récursives peuvent le faire!

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

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

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

il fonctionne très bien avec n'importe quelle langue, ici 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?)/';
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

Comparer "les 1519120920"

L'expression régulière ^((\w)(?:(?1)|\w?))$ faire le même travail, mais comme un oui/non à la place "contient".

PS: il utilise une définition où "o" n'est pas un palimbrome, "able-elba" format hyphened n'est pas un palindrome, mais "ableelba" est. La nommer definition1 .

quand " o " et "able-elba "sont des palindrones, nommant definition2 .

la Comparaison avec un autre "palindrome regexes",

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

• ^((.)(?1)?|.)$ ( @LilDevil ) utiliser definition2 (accepte " o " et "able-elba" ainsi différant également dans la reconnaissance des cordes "aaaaa" et "bbbb").

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

• ^((.)(?1)*|.?)$ ( @Csaba ) utiliser definition2 .

---

NOTE: pour comparer Vous pouvez ajouter plus de mots à $subjects et une ligne pour chaque regex comparé,

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

comme souligné par ZCHudson , déterminer si quelque chose est un palindrome ne peut pas être fait avec un regexp habituel, comme l'ensemble de palindrome n'est pas une langue régulière.

je suis totalement en désaccord avec Airsource Ltd quand il dit que "c'est pas possibles" n'est pas le genre de réponse que l'enquêteur est à la recherche pour. Pendant mon entretien, j'arrive à ce genre de question quand 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 engager quelqu'un qui va essayer de faire quelque chose de la mauvaise façon, si il sait mieux.

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

je voudrais expliquer à l'interviewer que le langage composé de palindromes n'est pas un langage régulier mais plutôt sans contexte.

l'expression régulière qui correspondrait à tous les palindromes serait infinite . 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 utiliser au minimum un certain type de NDPA, ou tout simplement utiliser la technique simple chaîne de renversement/égal.

le mieux que l'on puisse faire avec regexes, avant de manquer de groupes de capture:

/(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?).?/

tous les palindromes jusqu'à 19 caractères.

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

str == str.reverse ? true : false

Je n'ai pas encore de Représentant pour commenter en ligne, mais le regex fourni par MizardX, et modifié par Csaba, peut être modifié davantage pour le faire fonctionner en PCRE. Le seul échec que j'ai trouvé est la chaîne monochrome, mais je peux le tester séparément.

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

si vous pouvez le faire échouer sur d'autres chaînes, s'il vous plaît 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 =~ /(.)(.)./ ){
    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 n'importe quelle longueur ( parce que cela exige quantité infinie de mémoire). Mais il est possible de faire correspondre des Paliandromes de longueur fixe. Dire, il est possible d'écrire une expression régulière qui correspond à toutes 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])\b pour correspondre à des mots palindrome tels que a, dad, radar, racecar, and redivider . ps: ce regex ne correspond qu'à des mots palindrome qui sont un nombre impair de lettres longues.

voyons comment ce regex correspond au radar. Le mot boundary \B correspond au début de la chaîne. Le moteur regex entre dans le groupe de capture "word". [A-z] correspond à r qui est ensuite stocké dans la pile pour le groupe de capture "lettre" au niveau de récursion zéro. Maintenant le moteur regex entre dans le d'abord la récursivité du groupe "parole". (?'letter' [A-z]) correspond et capture a au niveau de récursion 1. Le regex entre la deuxième récursion du groupe "mot". (?'lettre'[a-z]) 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écursion échoue parce qu'il ne reste plus de caractères dans la chaîne pour que [A-z] corresponde. Le moteur regex doit faire marche arrière.

le moteur regex doit maintenant essayer le second alternative dans le groupe "mot". Le second [A-z] dans le regex correspond au dernier r dans la chaîne. Le moteur sort maintenant d'une récursion réussie, allant d'un niveau de retour à la troisième récursion.

après correspondance (&word) le moteur atteint \k'Letter+0'. Le backreference échoue parce que le moteur regex a déjà atteint la fin de la chaîne de caractères. Donc il recule une fois de plus. La deuxième alternative correspond maintenant au a. Le moteur regex sort du troisième récursivité.

le moteur regex a de nouveau correspondu (&word) et doit essayer le backreference à nouveau. Le backreference spécifie +0 ou le niveau actuel de récursion, qui est 2. À ce niveau, le groupe de capture correspond à d. Le backreference échoue parce que le prochain caractère de la chaîne est R. Retour 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 d'expressions régulières a il est arrivé à la première récursion au cours de laquelle le groupe de capture correspondait au premier A. Le moteur regex sort de la première recursion.

le moteur regex est maintenant de retour à l'extérieur de toute récursion. Que ce niveau, le groupe de capture stocké R. Le backreference peut maintenant correspondre au r final dans la chaîne. Puisque 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 du regex est atteint et radar est retourné comme la correspondance globale.

voici le code PL/SQL qui indique si une 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,'^(^.).*()$') = 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;

Un léger raffinement de Airsource Ltd méthode, en pseudo-code:

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

vous pouvez également le faire sans utiliser la récursion:

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

ou pour exclure la chaîne vide:

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

fonctionne avec Perl, PCRE, Ruby, Java

démo

mon $pal='malayalam';

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

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

correspond à des palindromes de 5 lettres comme refer et kayak. Il fait cela en utilisant (non-cupide) la correspondance de n'importe quelles trois lettres, suivie par les 2nd et 1st lettres appariées.

lien vers le site de regex101 utilisant ce