¿Cómo comprobar que una cadena es un palíndromo usando expresiones regulares?

93

Esa fue una pregunta de la entrevista que no pude responder:

¿Cómo comprobar que una cadena es un palíndromo usando expresiones regulares?

ps Ya existe una pregunta " ¿Cómo verificar si la cadena dada es palíndromo? " y da muchas respuestas en diferentes idiomas, pero ninguna respuesta que use expresiones regulares.

Degvik
fuente
1
stackoverflow.com/questions/3644266/… puede dar una idea.
Prakhar
2
Para la actualidad (2018) y para quién está buscando "la expresión regular palíndromo", consulte la discusión sobre PCRE que admite patrones recursivos en el enlace de Prakhar, y mi expresión regular recursiva a continuación, con comparaciones .
Peter Krauss

Respuestas:

151

La respuesta a esta pregunta es que "es imposible". Más específicamente, el entrevistador se pregunta si prestó atención en su clase de teoría computacional.

En su clase de teoría computacional aprendió sobre las máquinas de estados finitos. Una máquina de estados finitos se compone de nodos y aristas. Cada borde está anotado con una letra de un alfabeto finito. Uno o más nodos son nodos de "aceptación" especiales y un nodo es el nodo de "inicio". A medida que se lee cada letra de una palabra dada, atravesamos el borde dado en la máquina. Si terminamos en un estado de aceptación, decimos que la máquina "acepta" esa palabra.

Una expresión regular siempre se puede traducir a una máquina de estados finitos equivalente. Es decir, uno que acepta y rechaza las mismas palabras que la expresión regular (en el mundo real, algunos lenguajes regexp permiten funciones arbitrarias, estas no cuentan).

Es imposible construir una máquina de estados finitos que acepte todos los palíndromos. La prueba se basa en los hechos de que podemos construir fácilmente una cadena que requiera una cantidad arbitrariamente grande de nodos, es decir, la cadena

a ^ xba ^ x (p. ej., aba, aabaa, aaabaaa, aaaabaaaa, ....)

donde a ^ x es un x repetido. Esto requiere al menos x nodos porque, después de ver la 'b', tenemos que contar hacia atrás x veces para asegurarnos de que sea un palíndromo.

Finalmente, volviendo a la pregunta original, podría decirle al entrevistador que puede escribir una expresión regular que acepte todos los palíndromos que sean más pequeños que una longitud fija finita. Si alguna vez hay una aplicación del mundo real que requiera identificar palíndromos, es casi seguro que no incluirá los que son arbitrariamente largos, por lo que esta respuesta demostraría que puede diferenciar las imposibilidades teóricas de las aplicaciones del mundo real. Aún así, la expresión regular real sería bastante larga, mucho más larga que el programa equivalente de 4 líneas (ejercicio fácil para el lector: escriba un programa que identifique palíndromos).

José M Vidal
fuente
6
@SteveMoser En Ruby 1.9.x, las expresiones regulares ya no son Regulares (en el sentido de la Teoría de Autómatas) y, por lo tanto, es posible buscar palíndromos. Sin embargo, para las intenciones y propósitos, los palíndromos no se pueden verificar con una expresión regular regular (¿tiene sentido?).
1
@SteveMoser Hay una buena descripción del motor de expresiones regulares de Ruby ( >=1.9) aquí
@John tiene razón, así que en el contexto de la pregunta, José tiene razón y hqt está equivocado.
Steve Moser
2
En términos académicos, una expresión regular tiene límites específicos (define un DFA). En realidad, muchos motores de expresiones regulares (Perl y sus parientes principalmente) admiten referencias inversas que violan la definición académica (convirtiéndose en NFA o incluso más amplia). Entonces, esta pregunta tiene diferentes respuestas dependiendo del marco de referencia del interrogador.
jiggy
En una prueba oral deberías ir con "formalz es imposible", pero debes señalar que algunos motores de expresiones regulares lo permiten.
Oliver A.
46

Si bien el motor PCRE admite expresiones regulares recursivas (consulte la respuesta de Peter Krauss ), no puede usar una expresión regular en el motor ICU (como lo usa, por ejemplo, Apple) para lograr esto sin código adicional. Deberá hacer algo como esto:

Esto detecta cualquier palíndromo, pero requiere un bucle (que será necesario porque las expresiones regulares no pueden contar).

$a = "teststring";
while(length $a > 1)
{
   $a =~ /(.)(.*)(.)/;
   die "Not a palindrome: $a" unless $1 eq $3;
   $a = $2;
}
print "Palindrome";
Airsource Ltd
fuente
4
Buena respuesta. La pregunta no solicitó una sola expresión regular que detecte un palíndromo directamente desde el primer momento; simplemente solicitó un método para detectar palíndromos que utiliza expresiones regulares. Felicitaciones por su conocimiento para verlo de esta manera.
Stewart
1
Vea también la coincidencia más simple (sin manipulación de cadenas) usando solo una expresión regular, stackoverflow.com/a/48608623/287948
Peter Krauss
Gracias @PeterKrauss. No sabía que PCRE tenía recursividad. Hice referencia a su respuesta.
Airsource Ltd
32

No es posible. Los palíndromos no están definidos por un lenguaje regular. (Mira, aprendí algo en teoría computacional)

ZCHudson
fuente
2
La mayoría de los motores de expresiones regulares capturan más que los lenguajes regulares (net puede capturar paréntesis coincidentes, por ejemplo). Solo las expresiones regulares estándar están limitadas a los idiomas regulares.
Santiago Palladino
Sin embargo, la pregunta utilizó el término "expresión regular" ... así que la respuesta de ZCHudson es correcta.
paxos1977
2
@austirg: La respuesta de ZCHudson es correcta pero incompleta. Las expresiones regulares utilizadas en los lenguajes de programación modernos y las expresiones regulares utilizadas en las clases teóricas de CS son bestias diferentes. El término es solo un patrimonio histórico. Vea stackoverflow.com/questions/233243#235199 y mi respuesta.
jfs
2
@JF Sebastian - Tendría que estar de acuerdo con austirg en esto. Cuando el término expresión regular se usa sin que se mencione un lenguaje de programación específico, se aplica la definición de comp sci. No todos los lenguajes que admiten expresiones regulares pueden hacer esto, por lo que no debemos asumir que el que se usa aquí lo hace.
Rontólogo
@Rontólogo: No veo restricciones en la elección del lenguaje de programación en la pregunta, por lo que se permite cualquier idioma. Mire a la derecha: ¿cuál es el significado de "expresión regular" en las preguntas relacionadas? ¿Se menciona un lenguaje de programación específico en alguno de ellos?
jfs
27

Con Perl regex:

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

Aunque, como muchos han señalado, esto no puede considerarse una expresión regular si quieres ser estricto. Las expresiones regulares no admiten la recursividad.

Markus Jarderot
fuente
esto no funciona en PCRE (no coincide con "ababa"), pero funciona en Perl 5.10
newacct
Tienes razón. PCRE parece tratar la recursividad como un grupo atómico, mientras que Perl permite retroceder dentro de él. No creo que sea posible hacer esta verificación en PCRE.
Markus Jarderot
1
Sorprendentemente, no funciona para idiomas que no son latinos, por ejemplo, el idioma armenio.
Temujin
3
@Temujin Es porque los caracteres Unicode coinciden con los bytes codificados (agregue el /umodificador ), o porque los caracteres del combinador. (reemplazar .con la \Xsecuencia de escape ).
Markus Jarderot
1
Mi patrón no funciona en PCRE. Funciona en Perl. Su patrón falla cuando se repiten las subcadenas. Por ejemplo abababa. No es posible hacer que funcione con recursividad para cada entrada cuando se utilizan motores de expresiones regulares basados ​​en PCRE. Casimirs regex usa un enfoque diferente, usando iteración y estado mutable, y es bastante fascinante.
Markus Jarderot
15

Aquí hay uno para detectar palíndromos de 4 letras (por ejemplo: escritura), para cualquier tipo de personaje:

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

Aquí hay uno para detectar palíndromos de 5 letras (por ejemplo: radar), verificando solo letras:

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

Entonces parece que necesitamos una expresión regular diferente para cada longitud de palabra posible. Esta publicación en una lista de correo de Python incluye algunos detalles del por qué (autómatas de estado finito y lema de bombeo).

PARA
fuente
14

Dependiendo de qué tan seguro esté, le daría esta respuesta:

No lo haría con una expresión regular. No es un uso apropiado de expresiones regulares.

Jon Skeet
fuente
3
Espero que me dé un poco más de explicación para demostrar que realmente comprende las limitaciones de las expresiones regulares. Su simple respuesta podría tomarse como "Estoy perplejo".
Scott Wegner
De ahí la cláusula depend que dio.
Will Bickford
13

¡Sí , puedes hacerlo en .Net!

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

¡Puedes comprobarlo aquí ! ¡Es una publicación maravillosa!

kev
fuente
El objetivo de Regex con sabor a .NET es que no son regulares porque no son autómatas de estado finito; no son realmente expresiones regulares en el sentido teórico.
gato
12

StackOverflow está lleno de respuestas como "¿Expresiones regulares? No, no lo admiten. No pueden admitirlo".

La verdad es que las expresiones regulares ya no tienen nada que ver con las gramáticas regulares . Las expresiones regulares modernas presentan funciones como la recursividad y los grupos de equilibrio, y la disponibilidad de sus implementaciones es cada vez mayor (consulte los ejemplos de Ruby aquí, por ejemplo). En mi opinión, aferrarse a la vieja creencia de que las expresiones regulares en nuestro campo son cualquier cosa menos un concepto de programación es simplemente contraproducente. En lugar de odiarlos por la elección de palabras que ya no es la más apropiada, es hora de que aceptemos las cosas y sigamos adelante.

Aquí hay una cita de Larry Wall , el creador del propio Perl:

(…) Generalmente tiene que ver con lo que llamamos “expresiones regulares”, que están relacionadas sólo marginalmente con expresiones regulares reales. Sin embargo, el término ha crecido con las capacidades de nuestros motores de coincidencia de patrones, por lo que no voy a intentar luchar contra la necesidad lingüística aquí. Sin embargo, generalmente los llamaré "regexes" (o "regexen", cuando estoy de humor anglosajón).

Y aquí hay una publicación de blog de uno de los desarrolladores principales de PHP :

Como el artículo era bastante extenso, aquí un resumen de los puntos principales:

  • Las "expresiones regulares" utilizadas por los programadores tienen muy poco en común con la noción original de regularidad en el contexto de la teoría del lenguaje formal.
  • Las expresiones regulares (al menos PCRE) pueden coincidir con todos los lenguajes libres de contexto. Como tales, también pueden coincidir con HTML bien formado y casi todos los demás lenguajes de programación.
  • Las expresiones regulares pueden coincidir con al menos algunos lenguajes sensibles al contexto.
  • La coincidencia de expresiones regulares es NP-completa. Como tal, puede resolver cualquier otro problema NP utilizando expresiones regulares.

Dicho esto, puede hacer coincidir palíndromos con expresiones regulares usando esto:

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

... que obviamente no tiene nada que ver con las gramáticas regulares.
Más información aquí: http://www.regular-expressions.info/balancing.html

rr-
fuente
9

Como algunos ya han dicho, no hay una expresión regular única que detecte un palíndromo general fuera de la caja, pero si desea detectar palíndromos hasta una cierta longitud, puede usar algo como

(.?)(.?)(.?)(.?)(.?).?\5\4\3\2\1
Stewart
fuente
7

Ahora se puede hacer en Perl. Usando referencia recursiva:

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

modificado en base a la casi última parte http://perldoc.perl.org/perlretut.html

Hui Liu
fuente
6

En ruby ​​puede utilizar grupos de captura con nombre. entonces algo como esto funcionará -

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

Pruébalo, funciona ...

1.9.2p290 :017 > palindrome?("racecar")
 => "racecar" 
1.9.2p290 :018 > palindrome?("kayak")
 => "kayak" 
1.9.2p290 :019 > palindrome?("woahitworks!")
 => nil 
Taylor
fuente
1
Los grupos de captura con nombre no son estrictamente expresiones regulares. willamette.edu/~fruehr/LLC/lab5.html
Steve Moser
2
Estás en lo correcto. Es por eso específicamente que le indiqué que tendría que usar grupos de captura con nombre.
Taylor
¿Podría alguien por casualidad explicar ese RE personaje por personaje para un novato? Entiendo todo lo siguiente (las comas separan los 'átomos') /, \ A, (, |, \ w, |, (, (, \ w,),),), \ z, /, x pero no ¿No entiendes ninguno de estos? <p>,?:,? <l>, \ g <p>, \ k <l + 0> y estoy usando rubular.com para obtener ayuda y parece entender el RE ( naturalmente), pero eso no me ayuda a verlo, e incluso "Para obtener una guía completa de expresiones regulares de Ruby, consulte el Pickaxe". no ayuda, porque el sitio vinculado con 'Pickaxe' no explica los átomos que no entiendo. Lo sé ? SIGUIENTE a coincidencias Cero o una de a, pero? precede a un personaje?
Kevin Ford el submarinista
¡Ah, grupos de captura con nombre ! Agradable. @SteveMoser ahora es un enlace roto, pero encontré otro . Gracias Taylor por mencionarlos, de lo contrario, no habría tenido idea de lo que significa? <p> y? <l> y?: (Grupo de captura sin captura) y \ g <p> y \ k <l + 0>. ¿Todavía no puedo ver qué? <p> | es sin embargo. No lo hace | significa "o"? No puedo encontrar documentación de ese uso para la tubería en RE. Todavía estaría encantado de ver una explicación detallada de este RE tan agradable.
Kevin Ford el submarinista
5

En realidad, es más fácil hacerlo con manipulación de cadenas en lugar de expresiones regulares:

bool isPalindrome(String s1)

{

    String s2 = s1.reverse;

    return s2 == s1;
}

Me doy cuenta de que esto realmente no responde a la pregunta de la entrevista, pero podría usarlo para mostrar cómo conoce una mejor manera de hacer una tarea, y no es la típica "persona con un martillo, que ve cada problema como un clavo". . "

Dan
fuente
Si bien me gusta mucho esta respuesta, creo que obtendría puntos adicionales al usar BreakIterator para dividir correctamente la cadena en caracteres visuales.
Trejkaz
5

Aquí está mi respuesta al quinto nivel de Regex Golf (Un hombre, un plan). Funciona para hasta 7 caracteres con Regexp del navegador (estoy usando Chrome 36.0.1985.143).

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

Aquí hay uno para hasta 9 caracteres.

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

Para aumentar el número máximo de caracteres para el que funcionaría, lo reemplazaría repetidamente . con (?: (.).? \ n?)? .

pbatey
fuente
1
Logré ese con un poco menos de caracteres, ^ (.) (.) (.)?.? \ 3 \ 2 \ 1 $
Ben Ellis
Muchas gracias por estropearme :-)
U10-Forward
Por qué el resto de la gente tiene 13, pero esto es 19
U10-Forward
5

¡Las expresiones regulares recursivas pueden hacerlo!

Algoritmo tan simple y evidente para detectar una cadena que contiene un palíndromo:

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

En rexegg.com/regex-recursion, el tutorial explica cómo funciona.


Funciona bien con cualquier idioma, aquí un ejemplo adaptado de la misma fuente (enlace) como prueba de concepto, usando 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";
}

salidas

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

Comparando

La expresión regular ^((\w)(?:(?1)|\w?)\2)$ hace el mismo trabajo, pero como sí / no "contiene".
PD: está usando una definición en la que "o" no es un palimbromo, el formato con guiones "able-elba" no es un palíndromo, pero "ableelba" sí lo es. Nombrarlo definición 1 .
Cuando "o" y "able-elba" son palindrones, nombrar definition2 .

En comparación con otras "expresiones regulares palindrómicas",

  • ^((.)(?:(?1)|.?)\2)$la base-regex anterior sin \wrestricción, aceptando "capaz-elba".

  • ^((.)(?1)?\2|.)$( @LilDevil ) Use definition2 (acepta "o" y "able-elba", por lo que también difieren en el reconocimiento de las cadenas "aaaaa" y "bbbb").

  • ^((.)(?1)\2|.?)$( @Markus ) no se detectó "kook" ni "bbbb"

  • ^((.)(?1)*\2|.?)$( @Csaba ) Utilice la definición 2 .


NOTA: para comparar, puede agregar más palabras en $subjectsy una línea para cada expresión regular comparada,

  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";
Peter Krauss
fuente
5

También puede hacerlo sin utilizar la recursividad:

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

para permitir un solo carácter:

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

Funciona con Perl, PCRE

manifestación

Para Java:

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

manifestación

Casimir et Hippolyte
fuente
1
Esta es una respuesta muy interesante a una pregunta sobre expresiones regulares. En realidad, el único patrón que pasó algunas de mis pruebas . Gracias por este Casimir :)
bobble bubble
1
@bobblebubble: Gracias por su apoyo. Como puede ver, edité esta respuesta recientemente porque la versión anterior estaba equivocada (durante tres años, qué pena).
Casimir et Hippolyte
4

Con respecto a la expresión PCRE (de MizardX):

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

¿Lo has probado? En mi PHP 5.3 bajo Win XP Pro falla en: aaaba En realidad, modifiqué ligeramente la expresión de expresión para que se lea:

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

Creo que lo que está sucediendo es que mientras el par de personajes externos están anclados, los internos restantes no lo están. Esta no es toda la respuesta porque si bien transmite incorrectamente "aaaba" y "aabaacaa", falla correctamente en "aabaaca".

Me pregunto si hay una corrección para esto y también, ¿el ejemplo de Perl (por JF Sebastian / Zsolt) pasa mis pruebas correctamente?

Csaba Gabor desde Viena


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

es válido para motor Oniguruma (que se usa en Ruby)

tomado de Pragmatic Bookshelf

mpugach
fuente
3

En Perl (ver también la respuesta 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
}
jfs
fuente
2

Como señaló ZCHudson , determinar si algo es un palíndromo no se puede hacer con una expresión regular habitual, ya que el conjunto de palíndromos no es un lenguaje regular.

Estoy totalmente en desacuerdo con Airsource Ltd cuando dice que "no es posible" no es el tipo de respuesta que el entrevistador está buscando. Durante mi entrevista, llego a este tipo de preguntas cuando me enfrento a un buen candidato, para comprobar si puede encontrar el argumento correcto cuando le propusimos hacer algo mal. No quiero contratar a alguien que intente hacer algo de manera incorrecta si conoce mejor a alguien.

Nicolas
fuente
2

Le explicaría al entrevistador que el lenguaje que consiste en palíndromos no es un lenguaje regular sino que está libre de contexto.

La expresión regular que coincidiría con todos los palíndromos sería infinita . En cambio, le sugiero que se limite a aceptar un tamaño máximo de palíndromos; o si se necesitan todos los palíndromos, use como mínimo algún tipo de NDPA, o simplemente use la técnica simple de inversión de cadena / igual.

Fuego
fuente
2

Lo mejor que puede hacer con las expresiones regulares, antes de quedarse sin grupos de captura:

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

Esto coincidirá con todos los palíndromos de hasta 19 caracteres de longitud.

La resolución programática para todas las longitudes es trivial:

str == str.reverse ? true : false
Chris
fuente
Tu expresión regular no funciona. Por ejemplo, indicará que "abac" es una coincidencia ...
Darwin Airola
2

Todavía no tengo el representante para comentar en línea, pero la expresión regular proporcionada por MizardX y modificada por Csaba se puede modificar aún más para que funcione en PCRE. La única falla que he encontrado es la cadena de un solo carácter, pero puedo probarla por separado.

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

Si puede hacer que falle en cualquier otra cadena, comente.

Lil diablo
fuente
2
#!/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";
sapam
fuente
2

Desde la teoría de los autómatas es imposible igualar un paliandrome de cualquier longitud (porque eso requiere una cantidad infinita de memoria). Pero ES POSIBLE igualar Paliandromes de longitud fija. Digamos que es posible escribir una expresión regular que coincida con todos los paliandromes de longitud <= 5 o <= 6, etc., pero no> = 5, etc. donde el límite superior no está claro

Vijeenrosh PW
fuente
2

En Ruby puede usar \b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z])\bpara hacer coincidir palabras palíndromo comoa, dad, radar, racecar, and redivider . ps: esta expresión regular solo coincide con las palabras palíndromo que tienen un número impar de letras.

Veamos cómo esta expresión regular coincide con el radar. La palabra límite \ b coincide con el comienzo de la cadena. El motor de expresiones regulares ingresa al grupo de captura "palabra". [az] coincide con r que luego se almacena en la pila para el grupo de captura "letra" en el nivel de recursividad cero. Ahora el motor de expresiones regulares entra en la primera recursividad del grupo "palabra". (? 'letra' [az]) coincide y captura a en el nivel de recursividad uno. La expresión regular entra en la segunda recursión del grupo "palabra". (? 'letra' [az]) captura d en el nivel de recursividad dos. Durante las siguientes dos recursiones, el grupo captura a y r en los niveles tres y cuatro. La quinta recursión falla porque no quedan caracteres en la cadena para que [az] coincida. El motor de expresiones regulares debe retroceder.

El motor de expresiones regulares ahora debe probar la segunda alternativa dentro del grupo "palabra". La segunda [az] de la expresión regular coincide con la r final de la cadena. El motor ahora sale de una recursión exitosa, retrocediendo un nivel hasta la tercera recursión.

Después de hacer coincidir (& word) el motor llega a \ k'letter + 0 '. La referencia inversa falla porque el motor de expresiones regulares ya ha llegado al final de la cadena de asunto. Así que retrocede una vez más. La segunda alternativa ahora coincide con a. El motor de expresiones regulares sale de la tercera recursión.

El motor de expresiones regulares ha vuelto a coincidir (& word) y debe intentar la referencia inversa nuevamente. La referencia inversa especifica +0 o el nivel actual de recursividad, que es 2. En este nivel, el grupo de captura coincide con d. La referencia inversa falla porque el siguiente carácter de la cadena es r. Retrocediendo de nuevo, la segunda alternativa coincide d.

Ahora, \ k'letter + 0 'coincide con la segunda a en la cadena. Esto se debe a que el motor de expresiones regulares ha regresado a la primera recursión durante la cual el grupo de captura coincidió con la primera a. El motor de expresiones regulares sale de la primera recursión.

El motor de expresiones regulares ahora está fuera de toda recursividad. Que este nivel, el grupo de captura almacenó r. La referencia inversa ahora puede coincidir con la r final de la cadena. Dado que el motor ya no está dentro de ninguna recursividad, continúa con el resto de la expresión regular después del grupo. \ b coincide con el final de la cadena. Se alcanza el final de la expresión regular y el radar se devuelve como coincidencia general.

Melih Altıntaş
fuente
2

aquí está el código PL / SQL que dice si la cadena dada es palíndromo o no usando expresiones regulares:

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;
ankush
fuente
2
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";
}
Kanchan Sen Laskar
fuente
2
Si bien este código puede responder a la pregunta, proporcionar un contexto adicional sobre cómo y / o por qué resuelve el problema mejoraría el valor de la respuesta a largo plazo.
Donald Duck
2

Esta expresión regular detectará palíndromos de hasta 22 caracteres ignorando espacios, tabulaciones, comas y comillas.

\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

Juega con él aquí: https://regexr.com/4tmui

Tony Tonev
fuente
0

Un ligero refinamiento del método de Airsource Ltd, en pseudocódigo:

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