Comment vérifier qu'une chaîne est un palindrome l'aide d'expressions régulières?
C'était une question d'entrevue que j'étais 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 "Comment vérifier si la chaîne est palindrome?" et il donne beaucoup de réponses dans les différentes langues, mais pas de réponse qui utilise des expressions régulières.
- stackoverflow.com/questions/3644266/... peut donner une idée.
- Pour aujourd'hui (2018) et qui est à la recherche pour "le palindrome regex", voir la discussion à propos de PCRE de soutien récursive modèles à Prakhar du lien, et mon récursive regex ci-dessous, avec des comparaisons.
Vous devez vous connecter pour publier un commentaire.
La réponse à cette question est que "c'est impossible". Plus précisément, l'interviewer demande si vous avez payé l'attention dans votre calcul de la théorie de la classe.
Dans votre calcul de la théorie de la classe que vous avez appris à propos des machines à états finis. Une machine à états finis est composé de nœuds et d'arêtes. Chaque arête est annoté avec une lettre d'un alphabet fini. Un ou plusieurs nœuds spéciaux "en acceptant" nœuds et un nœud est le "début" de nœud. Comme chaque lettre est lue à partir d'un mot donné, nous traverse le bord de la machine. Si nous nous retrouvons dans un état acceptant alors nous disons que la machine "accepte" de ce mot.
Une expression régulière peut toujours être traduite en un équivalent de la machine à état fini. Qui est, celui qui accepte et rejette les mêmes mots que l'expression régulière (dans le monde réel, certains regexp langues permettre de fonctions arbitraires, elles 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 qui implique un nombre arbitrairement grand de nœuds, à savoir la chaîne
a^x b a^x (eg., aba, aabaa, aaabaaa, aaaabaaaa, ....)
où a^x est un répétée x fois. Cela nécessite au moins x nœuds, car, après avoir vu le 'b', nous devons compter de retour x fois pour s'assurer qu'il est un palindrome.
Enfin, pour en revenir à la question initiale, vous pourriez dire à l'intervieweur que vous pouvez écrire une expression régulière qui accepte tous les palindromes qui sont inférieures à une certaine longueur fixe. Si il n'y a jamais une véritable application qui nécessite l'identification des palindromes, puis elle sera presque certainement pas inclure arbitrairement longues, donc cette réponse serait de montrer que vous pouvez différencier les impossibilités théoriques à partir des applications du monde réel. Encore, la regexp serait très long, beaucoup plus que l'équivalent de 4 lignes de programme (exercice facile pour le lecteur: écrire un programme qui identifie les palindromes).
>=1.9
) iciTandis que le PCRE moteur prend en charge récursive des expressions régulières (voir la réponse de Peter Krauss), vous ne pouvez pas utiliser une regex sur le ICU moteur (comme, par exemple, par Apple) d'atteindre cet objectif sans code supplémentaire. Vous aurez besoin de faire quelque chose comme ceci:
Cette détecte un palindrome, mais nécessite une boucle (qui sera nécessaire, car les expressions régulières ne pouvez pas compter).
Il n'est pas possible. Palindromes ne sont pas définies par un langage régulier. (Voir, j'ai appris quelque chose de calcul dans la théorie)
Avec l'expression rationnelle Perl:
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 prend pas en charge la récursivité.
/u
modificateur), ou en raison de combinateur de caractères. (remplacer.
avec le\X
séquence d'échappement).Voici de détecter 4-lettre de palindromes (par exemple: acte), pour n'importe quel type de personnage:
Voici de détecter 5-lettre de palindromes (par exemple: radar), la vérification des lettres seulement:
Il semble donc que nous avons besoin d'un autre regex pour chaque mot de longueur.
Ce post sur un Python liste de diffusion comprend quelques détails pourquoi (Automates d'états Finis et lemme de pompage).
Selon le degré de confiance que vous êtes, je voudrais donner cette réponse:
Oui, vous pouvez le faire dans .Net!
Vous pouvez le vérifier ici! C'est un magnifique message!
Comme quelques-uns l'ont déjà dit, il n'y a pas regexp qui va détecter un général palindrome hors de la boîte, mais si vous voulez détecter des palindromes jusqu'à une certaine longueur, vous pouvez utiliser quelque chose comme
StackOverflow est plein de réponses comme "les expressions Régulières? non, ils ne le supporte pas. Ils ne peut pas soutenir.".
La vérité est que expressions régulières n'ont rien à voir avec régulière des grammaires plus. Moderne expressions régulières fonctions telles que la récursivité et l'équilibrage des groupes, et de la disponibilité de leur mise en œuvre ne cesse de croître (voir Ruby exemples ici, par exemple). À mon avis, de s'accrocher à la vieille croyance que les expressions régulières dans notre domaine sont rien, mais une programmation concept est 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 un citation de Larry Wall, le créateur de Perl lui-même:
Et voici un post de blog par l'un des développeurs PHP à la base:
Cela étant dit, vous pouvez faire correspondre les palindromes avec regexes en utilisant ceci:
...ce qui n'a évidemment rien à voir avec régulièrement des grammaires.
Plus d'infos ici: http://www.regular-expressions.info/balancing.html
Il peut être fait en Perl maintenant. Utilisation récursive de référence:
modifiés en fonction de la proximité de la dernière partie http://perldoc.perl.org/perlretut.html
En ruby, vous pouvez utiliser nommé groupes de capture. donc, quelque chose comme cela fonctionne -
l'essayer, ça fonctionne...
Voici ma réponse à Regex de Golf de niveau 5 (Un homme, un plan). Il travaille jusqu'à 7 caractères avec le navigateur Regexp (je suis en utilisant google Chrome 36.0.1985.143).
Voici une pour un maximum de 9 caractères
Pour augmenter le nombre maximum de caractères qu'il fallait pour, vous auriez à plusieurs reprises remplacer .? avec (?:(.).?\n?)?.
c'est valable pour Oniguruma moteur (qui est utilisé en Ruby)
a eu de la Pragmatique Bookshelf
Il est effectivement plus facile de le faire avec la manipulation de la chaîne plutôt que les expressions régulières:
Je me rends compte ce n'est pas vraiment répondre à la question de l'entrevue, mais vous pouvez l'utiliser pour montrer comment vous connaissez un meilleur moyen de faire une tâche, et vous n'êtes pas le typique "personne avec un marteau, qui voit chaque problème comme un clou."
En Perl (voir aussi Zsolt Botykai réponse):
Concernant le PCRE expression (à partir de MizardX):
/^((.)(?1)\2|.?)$/
Avez-vous testé? Sur mon PHP 5.3 sous Win XP Pro, il échoue sur: aaaba
En fait, j'ai modifié l'expression expression légèrement, à lire:
/^((.)(?1)*\2|.?)$/
Je pense que ce qui se passe est que, tandis que la paire extérieure de personnages sont ancrés, les autres ceux de l'intérieur ne le sont pas. Ce n'est pas tout à fait l'ensemble de la réponse, car tandis qu'il passe de manière incorrecte sur "aaaba" et "aabaacaa", elle ne parviennent pas correctement sur "aabaaca".
Je me demande si il y a une correction pour cela, et aussi,
Le Perl exemple (par JF Sebastian /Zsolt) passer mes tests correctement?
Csaba Gabor de Vienne
Récursive des Expressions Régulières peut le faire!
Tellement simple et évident algorithme pour détecter une chaîne de caractères qui contient un palindrome:
À rexegg.com/regex-recursion le tutoriel explique comment il fonctionne.
Il fonctionne très bien avec n'importe quelle langue, voici un exemple adapté à partir de la même source (lien) comme une preuve de concept, à l'aide de PHP:
sorties
Comparant
L'expression régulière
^((\w)(?:(?1)|\w?)\2)$
faire le même travail, mais comme un oui/non à la place "contient".PS: c'est à l'aide d'une définition où le "o" n'est pas un palimbrome, "mesure-de l'île d'elbe" hyphened format n'est pas un palindrome, mais "ableelba" est. En le nommant definition1.
Lorsque "o" et "mesure-de l'île d'elbe" sont palindrones, naming definition2.
En comparant avec un autre "palindrome regexes",
^((.)(?:(?1)|.?)\2)$
la base-regex ci-dessus sans\w
restriction, en acceptant "en mesure-de l'île d'elbe".^((.)(?1)?\2|.)$
(@LilDevil) Utilisation definition2 (accepte le "o" et "mesure-de l'île d'elbe" si différents aussi dans la reconnaissance de "aaaaa" et "bbbb" chaînes de caractères).^((.)(?1)\2|.?)$
(@Markus) non détecté "kook" ni "bbbb"^((.)(?1)*\2|.?)$
(@Csaba) Utilisation definition2.REMARQUE: pour comparer, vous pouvez ajouter plus de mots à
$subjects
et une ligne pour chaque rapport regex,Comme l'a souligné ZCHudson, de déterminer si quelque chose est un palindrome ne peut pas être fait avec un regexp, comme l'ensemble des 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 possibles" n'est pas le genre de réponse que l'enquêteur est à la recherche pour. Lors de mon entretien, j'en 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 la langue composée de palindromes n'est pas un langage régulier, mais plutôt libre de tout contexte.
L'expression régulière correspondant à tous les palindromes serait infini. Au lieu de cela, je voudrais suggérer qu'il se limiter à 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 une simple chaîne de retournement/est égal à la technique.
Le meilleur que vous pouvez faire avec regexes, avant d'exécuter des groupes de capture:
Tous les palindromes jusqu'à 19 caractères.
Programatcally de résolution pour toutes les longueurs est trivial:
Je n'ai pas de rep pour commenter inline encore, mais l'expression régulière fournie par MizardX, et modifié par Csaba, peut être modifié pour le faire fonctionner dans PCRE. La seule panne que j'ai trouvé est la seule chaîne de char, mais je peux tester pour que séparément.
/^((.)(?1)?\2|.)$/
Si vous pouvez le faire échouer sur toutes les chaînes, s'il vous plaît commentaire.
À partir de la théorie des automates est impossible de faire correspondre un paliandrome de longueur ( car cela nécessite une quantité infinie de mémoire). Mais IL EST POSSIBLE de faire correspondre 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 est difficile de
En Ruby, vous pouvez utiliser
\b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z])\b
pour correspondre à palindrome des mots tels quea, dad, radar, racecar, and redivider
. ps : cette expression correspond uniquement aux palindrome mots qui sont d'un nombre impair de lettres.Nous allons voir comment cette expression correspond à un radar. La limite de mot \b correspond au début de la chaîne. Le moteur d'expressions régulières entre la capture d'un groupe "parole". [a-z] correspond à r, ce qui est ensuite stockée dans la pile pour la capture d'un groupe "lettre" au niveau de récursivité zéro. Maintenant, le moteur d'expressions régulières entre dans la première récursivité du groupe "parole". (?'lettre'[a-z]) correspond à et capture un au niveau de récursivité un. La regex entre dans le deuxième récursivité du groupe "parole". (?'lettre'[a-z]) capture d au niveau de récursivité deux. Au cours des deux prochaines récurrences, le groupe saisit un et r à des niveaux trois et quatre. La cinquième récursivité échoue car il n'y a pas de caractères à gauche dans la chaîne de [a-z] pour correspondre. Le moteur d'expressions régulières doivent revenir en arrière.
Le moteur d'expressions régulières faut maintenant essayer la deuxième variante à l'intérieur du groupe "parole". La deuxième [a-z] dans l'expression régulière correspond à la finale r dans la chaîne. Le moteur de la sortie du succès de la récursivité, d'aller un niveau en arrière, jusqu'à la troisième récursivité.
Après la mise en correspondance (&mot) le moteur atteint \k'letter+0'. La référence arrière échoue parce que le moteur d'expressions régulières a déjà atteint la fin de la chaîne sujet. Donc, il revient une fois de plus. La deuxième solution, qui correspond maintenant à la une. Le moteur d'expressions régulières sorties de la troisième récursivité.
Le moteur d'expressions régulières a égalés (&mot) et les besoins de tenter la référence arrière à nouveau. La référence arrière spécifie +0 ou le niveau actuel de la récursivité, qui est de 2. À ce niveau, la capture d'un groupe apparié d. La référence arrière échoue parce que le caractère suivant dans la chaîne est r. Les retours en arrière encore une fois, la deuxième alternative correspond à. d.
Maintenant, \k'letter+0' correspond à la seconde dans la chaîne. C'est parce que le moteur d'expressions régulières est arrivé de retour à la première de la récursivité au cours de laquelle la capture d'un groupe apparié de la première. Le moteur d'expressions régulières sorties la première récursivité.
Le moteur d'expressions régulières est maintenant de retour à l'extérieur tous de la récursivité. À ce niveau, la capture d'un groupe stockées r. La référence arrière peut désormais match de la finale de la r dans la chaîne. Depuis que le moteur n'est pas à l'intérieur de toute la récursivité de plus, il procède avec le reste de la regex après le groupe. \b correspond à la fin de la chaîne. La fin de la regex est atteint et le radar est retourné comme l'ensemble du match.
voici le code PL/SQL qui indique si la chaîne est palindrome ou non à l'aide d'expressions régulières:
Vous pouvez aussi le faire sans l'aide de la récursivité:
ou à exclure de la chaîne vide:
Fonctionne avec Perl, PCRE, Ruby, Java
démo
Une légère raffinement de Airsource Ltd méthode, en pseudo-code:
mon $pal='malayalam';
\b([a-z])?([a-z])?([a-z])?\2\1\b/gi
Des matchs 5 de la lettre palindromes comme reporter et kayak. Il le fait à l'aide de (non-greedy) appariement de trois lettres, suivi par le 2e et le 1er appariés lettres.
Lien vers regex101 site à l'aide de cette
En JavaScript, il est fait en tapant