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

regex converter

Question

Esa fue una pregunta de entrevista que no pude responder:

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

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

Answer 1

¡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)$ el mismo trabajo, pero como sí / no, en su lugar "contiene".
PD: está usando una definición en la que "o" no es un palimbrome, el formato con guiones "able-elba" no es un palíndromo, sino que es "ableelba". Nombrarlo definición1 .
Cuando "o" y "poder-elba" son palindrones, nombrando definition2 .

Comparando con otras "expresiones regulares del palíndromo",

• ^((.)(?:(?1)|.?)/2)$ la base-regex anterior sin restricción /w , aceptando "able-elba".

• ^((.)(?1)?/2|.)$ ( share ) Usa definition2 (acepta "o" y "able-elba" por lo que difiere también en el reconocimiento de las cadenas "aaaaa" y "bbbb").

• ^((.)(?1)/2|.?)$ ( share ) no se detectó "kook" ni "bbbb"

• ^((.)(?1)*/2|.?)$ ( share ) Use definition2 .

NOTA: para comparar puede agregar más palabras a $subjects y 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";

Answer 2

Aquí está mi respuesta al quinto nivel de Regex Golf (Un hombre, un plan). Funciona con 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 los que funcionaría, lo reemplazará repetidamente . con (?: (.).? n?)? .

Answer 3

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

(.?)(.?)(.?)(.?)(.?).?/5/4/3/2/1

Answer 4

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

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 verificar si puede encontrar el argumento correcto cuando le propusimos que hiciera algo incorrecto. No quiero contratar a alguien que intente hacer algo incorrecto si conoce uno mejor.

Answer 5

Con Perl Regex:

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

Sin embargo, como muchos han señalado, esto no se puede considerar una expresión regular si quieres ser estricto. Las expresiones regulares no son compatibles con la recursividad.

Answer 6

De la teoría de los autómatas es imposible hacer coincidir un síndrome de cualquier longitud (porque eso requiere una cantidad infinita de memoria). Pero ES POSIBLE que coincida con 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

Answer 7

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
}

Answer 8

En Ruby puedes usar /b(?''word''(?''letter''[az])/g''word''/k''letter+0''|[az])/b para que coincida con las palabras típicas, como a, dad, radar, racecar, and redivider . ps: esta expresión regular solo coincide con palabras palídricas que son un número impar de letras largas.

Veamos cómo esta expresión regular coincide con el radar. La palabra límite / b coincide al comienzo de la cadena. El motor de expresiones regulares ingresa la "palabra" del grupo de captura. [az] coincide con r, que luego se almacena en la pila para la "letra" del grupo de captura en el nivel de recursión cero. Ahora el motor de expresiones regulares ingresa la primera recursión del grupo "palabra". (? ''letter'' [az]) coincide y captura a en el nivel de recursión uno. La expresión regular ingresa a la segunda recursión del grupo "palabra". (? ''letter'' [az]) capta d en el nivel de recursión 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". El segundo [az] en la expresión regular coincide con la r final de la cadena. El motor ahora sale de una recursión exitosa, pasando de un nivel a la tercera recursión.

Después de coincidir (y palabra) el motor alcanza / k''letter + 0 ''. La referencia posterior falla porque el motor de expresiones regulares ya ha alcanzado el final de la cadena de asunto. Entonces retrocede una vez más. La segunda alternativa ahora coincide con la a. El motor de expresiones regulares sale de la tercera recursión.

El motor de expresiones regulares ha vuelto a coincidir (& palabra) y necesita volver a intentar la retro-referencia. La referencia posterior especifica +0 o el nivel actual de recursión, que es 2. En este nivel, el grupo de captura coincide con d. La referencia posterior falla porque el siguiente caracter en la cadena es r. Retrocediendo de nuevo, la segunda alternativa coincide con d.

Ahora, / k''letter + 0 ''coincide con el segundo a de 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 el primero a. El motor de expresiones regulares sale de la primera recursión.

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

Answer 9

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 la pregunta de la entrevista, pero podrías usarla para mostrar cómo sabes una mejor manera de hacer una tarea, y no eres la típica "persona con un martillo", que ve cada problema como un clavo. "

Answer 10

En ruby ​​puedes usar 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 

Answer 11

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 tu clase de teoría computacional, aprendiste sobre máquinas de estados finitos. Una máquina de estados finitos se compone de nodos y bordes. Cada borde está anotado con una letra de un alfabeto finito. Uno o más nodos son nodos "aceptados" especiales y un nodo es el nodo "inicio". A medida que leemos cada letra de una palabra dada, atravesamos el borde dado en la máquina. Si terminamos en un estado de aceptación, entonces decimos que la máquina "acepta" esa palabra.

Una expresión regular siempre se puede traducir a una máquina de estados finita equivalente. Es decir, uno que acepta y rechaza las mismas palabras que la expresión regular (en el mundo real, algunos lenguajes de expresiones regulares permiten funciones arbitrarias, que 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 requiere un número arbitrariamente grande de nodos, a saber, la cadena

a ^ xba ^ x (por ejemplo, aba, aabaa, aaabaaa, aaaabaaaa, ....)

donde a ^ x es una repetición x veces. Esto requiere al menos x nodos porque, después de ver la ''b'', tenemos que contar x veces para asegurarnos de que es 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 fija. Si alguna vez hay una aplicación en el mundo real que requiera la identificación de palíndromos, es casi seguro que no incluirá arbitrariamente a los largos, por lo tanto, esta respuesta mostrarí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 de 4 líneas equivalente (ejercicio fácil para el lector: escriba un programa que identifique los palíndromos).

Answer 12

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 su lugar, sugeriría que se limite a un tamaño máximo de palíndromos para aceptar; o si se necesitan todos los palíndromos, use al menos algún tipo de NDPA, o simplemente use la técnica de reversión de cadena simple / igual.

Answer 13

Lo mejor que puedes hacer con expresiones regulares, antes de que te quedes 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.

Programatcally resolver para todas las longitudes es trivial:

str == str.reverse ? true : false

Answer 14

No es posible. Palíndromos no están definidos por un lenguaje regular. (Ver, Hice algo en teoría computacional)

Answer 15

Respecto a la expresión PCRE (de MizardX):

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

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

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

Creo que lo que está sucediendo es que, mientras que el par de caracteres externo está anclado, los restantes interiores no. Esta no es toda la respuesta porque aunque incorrectamente pasa "aaaba" y "aabaacaa", falla correctamente en "aabaaca".

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

Csaba Gabor de Viena

Answer 16

Se puede hacer en Perl ahora. Usando referencia recursiva:

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

modificado en función de la última parte http://perldoc.perl.org/perlretut.html

Answer 17

Según la confianza que tengas, daría esta respuesta:

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

Answer 18

Si bien el motor PCRE admite expresiones regulares recursivas (vea la respuesta de Peter Krauss ), no puede usar una expresión regular en el motor de la ICU (como la utilizada, por ejemplo, Apple) para lograr esto sin código adicional. Tendrás que 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";

Answer 19

está lleno de respuestas como "¿Expresiones regulares? No, no las admiten. No pueden soportarlo".

La verdad es que las expresiones regulares ya no tienen nada que ver con las gramáticas regulares . Las funciones de expresiones regulares modernas incluyen funciones como la recursión y el equilibrio de grupos, y la disponibilidad de sus implementaciones es cada vez mayor (ver 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 de Perl:

(...) generalmente tiene que ver con lo que llamamos "expresiones regulares", que solo están relacionadas marginalmente con expresiones regulares reales. Sin embargo, el término ha crecido con las capacidades de nuestros motores de combinación de patrones, por lo que no voy a tratar de luchar contra la necesidad lingüística aquí. Sin embargo, los llamaré generalmente "regexes" (o "regexen", cuando estoy en un estado de ánimo anglosajón).

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

Como el artículo fue 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 idiomas libres de contexto. Como tales, también pueden combinar HTML bien formado y casi todos los demás lenguajes de programación.
• Las expresiones regulares pueden coincidir al menos con algunos lenguajes contextuales.
• La coincidencia de expresiones regulares es NP-completa. Como tal, puede resolver cualquier otro problema NP utilizando expresiones regulares.

Dicho esto, puedes 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

Answer 20

También puede hacerlo sin usar recursión:

/A(?:(.)(?=.*?(/1/2?)/z))*?.?/2/z

o para excluir la cadena vacía:

/A(?=.)(?:(.)(?=.*?(/1/2?)/z))*?.?/2/z

Funciona con Perl, PCRE, Ruby, Java

demo

Answer 21

Todavía no tengo el representante para comentar en línea, pero la expresión regular proporcionada por MizardX y modificada por Csaba puede modificarse aún más para que funcione en PCRE. La única falla que he encontrado es la cadena de caracteres únicos, pero puedo probar eso por separado.

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

Si puede hacer que falle en otras cadenas, coméntelo.

Answer 22

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

Answer 23

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

Answer 24

aquí está el código PL / SQL que dice si la cadena dada es palindrome o no usa 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;

Answer 25

mi $ 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 26

Here''s uno para detectar palíndromos de 4 letras (p. Ej .: escritura), para cualquier tipo de personaje:

/(./)/(./)/2/1

Here''s uno para detectar los palíndromos de 5 letras (p. Ej .: radar), solo para buscar 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 sobre por qué (autómatas estatales finitos y lema de bombeo).

Answer 27

/b([az])?([az])?([az])?/2/1/b/gi

Coincide con palíndromos de 5 letras como referir y kayak. Hace esto usando una correspondencia (no codiciosa) de tres letras, seguida de la segunda y la primera letras coincidentes.

Enlace al sitio regex101 usando esto

Answer 28

Sí , puedes hacerlo en .Net!

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

¡Puedes verificarlo here ! ¡Es una publicación maravillosa!

Answer 29

#!/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 30

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

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

tomó de Pragmatic Bookshelf