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

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.

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).

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

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

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.

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).

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.

¡Sí , puedes hacerlo en .Net!

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

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

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

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

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

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 

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". . "

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?)? .

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

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

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

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

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

tomado de Pragmatic Bookshelf

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
}

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.

algo que puede hacer con perl: http://www.perlmonks.org/?node_id=577368

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.

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

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.

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

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

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.

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;

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

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

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