Como verificar se uma string é um palíndromo usando expressões regulares?

Essa foi uma pergunta da entrevista que eu não consegui responder:

Como verificar se uma string é um palíndromo usando expressões regulares?

ps Já existe uma pergunta " Como verificar se a string dada é palíndromo? " e dá muitas respostas em diferentes linguagens, mas nenhuma resposta que usa expressões regulares.

A resposta a esta pergunta é que "é impossível". Mais especificamente, o entrevistador está se perguntando se você prestou atenção em sua aula de teoria computacional.

Em sua aula de teoria computacional, você aprendeu sobre máquinas de estados finitos. Uma máquina de estados finitos é composta de nós e arestas. Cada aresta é anotada com uma letra de um alfabeto finito. Um ou mais nós são nós especiais de "aceitação" e um nó é o nó "inicial". À medida que cada letra é lida a partir de uma determinada palavra, atravessamos a borda fornecida na máquina. Se terminarmos em um estado de aceitação, diremos que a máquina "aceita" essa palavra.

Uma expressão regular sempre pode ser traduzida em uma máquina de estados finitos equivalente. Ou seja, aquele que aceita e rejeita as mesmas palavras que a expressão regular (no mundo real, algumas linguagens regexp permitem funções arbitrárias, estas não contam).

É impossível construir uma máquina de estados finitos que aceite todos os palíndromos. A prova se baseia no fato de que podemos facilmente construir uma string que requer um número arbitrariamente grande de nós, ou seja, a string

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

onde a ^ x é repetido x vezes. Isso requer pelo menos x nós porque, depois de ver o 'b', temos que voltar x vezes para nos certificarmos de que é um palíndromo.

Finalmente, voltando à pergunta original, você pode dizer ao entrevistador que pode escrever uma expressão regular que aceite todos os palíndromos menores do que um comprimento fixo finito. Se houver um aplicativo do mundo real que requer a identificação de palíndromos, é quase certo que ele não incluirá os arbitrariamente longos, portanto, essa resposta mostraria que você pode diferenciar impossibilidades teóricas de aplicativos do mundo real. Ainda assim, a regexp real seria bastante longa, muito mais longa do que o programa equivalente de 4 linhas (exercício fácil para o leitor: escrever um programa que identifica palíndromos).

Embora o mecanismo PCRE suporte expressões regulares recursivas (consulte a resposta de Peter Krauss ), você não pode usar uma regex no mecanismo ICU (como usado, por exemplo, pela Apple) para conseguir isso sem código extra. Você precisará fazer algo assim:

Isso detecta qualquer palíndromo, mas requer um loop (que será necessário porque as expressões regulares não podem contar).

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

Não é possível. Palíndromos não são definidos por uma linguagem regular. (Veja, eu aprendi algo em teoria computacional)

Com Perl regex:

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

Porém, como muitos apontaram, isso não pode ser considerado uma expressão regular se você quiser ser estrito. Expressões regulares não suportam recursão.

Aqui está um para detectar palíndromos de 4 letras (por exemplo: ação), para qualquer tipo de personagem:

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

Este é um para detectar palíndromos de 5 letras (por exemplo: radar), verificando apenas as letras:

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

Portanto, parece que precisamos de uma regex diferente para cada comprimento de palavra possível. Esta postagem em uma lista de discussão do Python inclui alguns detalhes do porquê (Autômatos de estado finito e lema do bombeamento).

Dependendo de quão confiante você esteja, eu daria esta resposta:

Eu não faria isso com uma expressão regular. Não é um uso apropriado de expressões regulares.

Sim , você pode fazer isso em .Net!

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

Você pode conferir aqui ! É um post maravilhoso!

StackOverflow está cheio de respostas como "Expressões regulares? Não, eles não suportam. Eles não podem suportar.".

A verdade é que as expressões regulares não têm mais nada a ver com gramáticas regulares . Expressões regulares modernas apresentam funções como recursão e grupos de balanceamento, e a disponibilidade de suas implementações está sempre crescendo (veja exemplos de Ruby aqui, por exemplo). Na minha opinião, manter a velha crença de que as expressões regulares em nosso campo são tudo menos um conceito de programação é contraproducente. Em vez de odiá-los pela escolha de palavras que não é mais a mais adequada, é hora de aceitarmos as coisas e seguir em frente.

Aqui está uma citação de Larry Wall , o criador do próprio Perl:

(…) Geralmente tendo a ver com o que chamamos de “expressões regulares”, que são apenas marginalmente relacionadas a expressões regulares reais. No entanto, o termo cresceu com as capacidades de nossos motores de correspondência de padrões, então não vou tentar lutar contra a necessidade linguística aqui. No entanto, geralmente os chamarei de “regexes” (ou “regexen”, quando estou no humor anglo-saxão).

E aqui está uma postagem no blog de um dos principais desenvolvedores de PHP :

Como o artigo era bastante longo, aqui um resumo dos pontos principais:

• As “expressões regulares” usadas pelos programadores têm muito pouco em comum com a noção original de regularidade no contexto da teoria da linguagem formal.
• Expressões regulares (pelo menos PCRE) podem corresponder a todas as linguagens livres de contexto. Como tal, eles também podem corresponder a HTML bem formado e praticamente todas as outras linguagens de programação.
• As expressões regulares podem corresponder a pelo menos algumas linguagens sensíveis ao contexto.
• A correspondência de expressões regulares é NP-completa. Assim, você pode resolver qualquer outro problema NP usando expressões regulares.

Dito isso, você pode combinar palíndromos com regexes usando:

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

... que obviamente não tem nada a ver com gramáticas regulares.
Mais informações aqui: http://www.regular-expressions.info/balancing.html

Como alguns já disseram, não há um regexp único que detecte um palíndromo geral fora da caixa, mas se você deseja detectar palíndromos até um determinado comprimento, pode usar algo como

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

Isso pode ser feito em Perl agora. Usando referência recursiva:

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

modificado com base na última parte http://perldoc.perl.org/perlretut.html

No ruby, você pode usar grupos de captura nomeados. então algo assim vai funcionar -

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

experimente, funciona ...

1.9.2p290 :017 > palindrome?("racecar")
 => "racecar" 
1.9.2p290 :018 > palindrome?("kayak")
 => "kayak" 
1.9.2p290 :019 > palindrome?("woahitworks!")
 => nil 

Na verdade, é mais fácil fazer isso com manipulação de string em vez de expressões regulares:

bool isPalindrome(String s1)

{

    String s2 = s1.reverse;

    return s2 == s1;
}

Sei que isso não responde realmente à pergunta da entrevista, mas você poderia usá-lo para mostrar que conhece uma maneira melhor de fazer uma tarefa, e você não é a típica "pessoa com um martelo, que vê todo problema como um prego . "

Aqui está minha resposta para o 5º nível do Regex Golf (um homem, um plano). Ele funciona para até 7 caracteres com o Regexp do navegador (estou usando o Chrome 36.0.1985.143).

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

Aqui está um para até 9 caracteres

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

Para aumentar o número máximo de caracteres para os quais ele funcionaria, você substituiria repetidamente . com (?: (.).? \ n?)? .

Expressões regulares recursivas podem fazer isso!

Algoritmo tão simples e evidente para detectar uma string que contém um palíndromo:

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

Em rexegg.com/regex-recursion, o tutorial explica como funciona.

Funciona bem com qualquer linguagem, aqui um exemplo adaptado da mesma fonte (link) como prova de conceito, 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";
}

saídas

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

A expressão regular ^((\w)(?:(?1)|\w?)\2)$ faz o mesmo trabalho, mas sim / não em vez de "contém".
PS: está usando uma definição onde "o" não é um palimbrome, o formato hifenizado "able-elba" não é um palíndromo, mas "ableelba" é. Nomeando-o como definição1 .
Quando "o" e "able-elba" são palíndrons, nomeando a definição 2 .

Comparando com outros "regexes de palíndromo",

• ^((.)(?:(?1)|.?)\2)$a base-regex acima sem \wrestrição, aceitando "able-elba".

• ^((.)(?1)?\2|.)$( @LilDevil ) Use a definição2 (aceita "o" e "able-elba", diferindo também no reconhecimento das strings "aaaaa" e "bbbb").

• ^((.)(?1)\2|.?)$( @Markus ) não detectou "kook" nem "bbbb"

• ^((.)(?1)*\2|.?)$( @Csaba ) Use a definição2 .

NOTA: para comparar, você pode adicionar mais palavras em $subjectse uma linha para cada regex 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";

Você também pode fazer isso sem usar recursão:

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

para permitir um único caractere:

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

Funciona com Perl, PCRE

demo

Para Java:

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

demo

Em relação à expressão PCRE (de MizardX):

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

Você já testou? No meu PHP 5.3 sob Win XP Pro falha em: aaaba Na verdade, eu modifiquei um pouco a expressão expression, para ler:

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

Acho que o que está acontecendo é que enquanto o par externo de personagens está ancorado, os internos restantes não estão. Esta não é toda a resposta, porque embora passe incorretamente "aaaba" e "aabaacaa", falha corretamente em "aabaaca".

Gostaria de saber se existe uma correção para isso, e também, o exemplo Perl (por JF Sebastian / Zsolt) passa meus testes corretamente?

Csaba Gabor de Viena

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

é válido para motor Oniguruma (que é usado em Ruby)

tirado da estante pragmática

Em Perl (veja também a resposta 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
}

Conforme apontado por ZCHudson , determinar se algo é um palíndromo não pode ser feito com uma regexp usual, pois o conjunto de palíndromos não é uma linguagem regular.

Discordo totalmente da Airsource Ltd quando ele diz que "não é possível" não é o tipo de resposta que o entrevistador está procurando. Durante a minha entrevista, chego a este tipo de questão quando me deparo com um bom candidato, para verificar se ele consegue encontrar o argumento certo quando lhe propomos fazer algo errado. Não quero contratar alguém que tentará fazer algo errado se conhecer melhor.

algo que você pode fazer com perl: http://www.perlmonks.org/?node_id=577368

Eu explicaria ao entrevistador que a linguagem que consiste em palíndromos não é uma linguagem regular, mas sim livre de contexto.

A expressão regular que corresponderia a todos os palíndromos seria infinita . Em vez disso, eu sugeriria que ele se restringisse a um tamanho máximo de palíndromos para aceitar; ou se todos os palíndromos forem necessários, use, no mínimo, algum tipo de NDPA, ou apenas use a técnica simples de reversão / igual.

O melhor que você pode fazer com regexes, antes de ficar sem grupos de captura:

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

Isso corresponderá a todos os palíndromos com até 19 caracteres de comprimento.

A solução programática para todos os comprimentos é trivial:

str == str.reverse ? true : false

Não tenho o representante para comentar inline ainda, mas a regex fornecida pelo MizardX e modificada pelo Csaba pode ser modificada ainda mais para que funcione no PCRE. A única falha que encontrei é a string de um único caractere, mas posso testar isso separadamente.

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

Se você pode fazer com que ele falhe em qualquer outra string, por favor, 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";

Da teoria dos autômatos é impossível combinar uma síndrome de paralisia de qualquer tamanho (porque isso requer uma quantidade infinita de memória). Mas É POSSÍVEL combinar Paliandromes de Comprimento Fixo. Digamos que seja possível escrever uma regex que corresponda a todos os paliandromes de comprimento <= 5 ou <= 6 etc, mas não> = 5 etc, onde o limite superior não é claro

Em Ruby, você pode usar \b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z])\bpara combinar palavras do palíndromo, como a, dad, radar, racecar, and redivider. ps: esta regex só corresponde a palavras do palíndromo com um número ímpar de letras.

Vamos ver como esse regex corresponde ao radar. O limite da palavra \ b corresponde ao início da string. O mecanismo regex insere o grupo de captura "palavra". [az] corresponde a r que é então armazenado na pilha para a "letra" do grupo de captura no nível de recursão zero. Agora, o motor regex entra na primeira recursão do grupo "palavra". (? 'letter' [az]) corresponde e captura a no nível de recursão um. A regex entra na segunda recursão do grupo "palavra". (? 'letter' [az]) captura d no nível de recursão dois. Durante as próximas duas recursões, o grupo captura a e r nos níveis três e quatro. A quinta recursão falha porque não há caracteres restantes na string para [az] corresponder. O mecanismo regex deve retroceder.

O motor regex deve agora tentar a segunda alternativa dentro do grupo "palavra". O segundo [az] na regex corresponde ao r final na string. O mecanismo agora sai de uma recursão bem-sucedida, voltando um nível até a terceira recursão.

Depois de combinar (& palavra), o mecanismo atinge \ k'letter + 0 '. A referência anterior falha porque o mecanismo regex já atingiu o final da string de assunto. Então, ele volta mais uma vez. A segunda alternativa agora corresponde a a. O mecanismo regex sai da terceira recursão.

O mecanismo regex correspondeu novamente (& word) e precisa tentar a referência anterior novamente. A referência anterior especifica +0 ou o nível atual de recursão, que é 2. Nesse nível, o grupo de captura correspondeu a d. A referência anterior falha porque o próximo caractere na string é r. Retrocedendo novamente, a segunda alternativa corresponde a d.

Agora, \ k'letter + 0 'casa com o segundo a na string. Isso ocorre porque o mecanismo regex voltou à primeira recursão durante a qual o grupo de captura correspondeu ao primeiro a. O mecanismo regex sai da primeira recursão.

O mecanismo regex agora está fora de toda recursão. Nesse nível, o grupo de captura armazenou r. A referência anterior agora pode corresponder ao r final na string. Uma vez que o motor não está mais dentro de nenhuma recursão, ele continua com o restante da regex após o grupo. \ b corresponde ao final da string. O final da regex é alcançado e o radar é retornado como a correspondência geral.

aqui está o código PL / SQL que informa se determinada string é palíndromo ou não usa expressões 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";
}

Este regex detectará palíndromos de até 22 caracteres, ignorando espaços, tabulações, vírgulas e aspas.

\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

Brinque com ele aqui: https://regexr.com/4tmui

Um ligeiro refinamento do método da Airsource Ltd, em pseudocódigo:

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