Come verificare che una stringa sia palindromo usando le espressioni regolari?

Era una domanda di intervista a cui non ero in grado di rispondere:

Come verificare che una stringa sia palindromo usando le espressioni regolari?

ps C’è già una domanda ” Come verificare se la stringa data è palindrome? ” e fornisce molte risposte in lingue diverse, ma nessuna risposta che usa espressioni regolari.

La risposta a questa domanda è che “è imansible”. Più specificamente, l’intervistatore si chiede se tu abbia prestato attenzione nella tua lezione di teoria computazionale.

Nella tua lezione di teoria computazionale hai imparato a conoscere le macchine a stati finiti. Una macchina a stati finiti è composta da nodes e spigoli. Ogni spigolo è annotato con una lettera da un alfabeto finito. Uno o più nodes sono nodes “accettanti” speciali e un nodo è il nodo “inizio”. Mentre ogni lettera viene letta da una determinata parola, attraversiamo il bordo specificato nella macchina. Se finiamo in uno stato accettante, diciamo che la macchina “accetta” quella parola.

Un’espressione regolare può sempre essere tradotta in una macchina a stati finiti equivalente. Cioè, uno che accetta e rifiuta le stesse parole dell’espressione regolare (nel mondo reale, alcuni linguaggi regexp consentono funzioni arbitrarie, questi non contano).

È imansible build una macchina a stati finiti che accetti tutti i palindromi. La dimostrazione si basa sul fatto che possiamo facilmente build una stringa che richiede un numero arbitrariamente grande di nodes, vale a dire la stringa

a ^ xba ^ x (ad es., aba, aabaa, aaabaaa, aaaabaaaa, ….)

dove a ^ x è ripetuto x volte. Questo richiede almeno x nodes perché, dopo aver visto la ‘b’, dobbiamo contare indietro x volte per essere sicuri che sia un palindromo.

Infine, tornando alla domanda originale, potresti dire all’intervistatore che puoi scrivere un’espressione regolare che accetta tutti i palindromi che sono più piccoli di una lunghezza fissa finita. Se mai esistesse un’applicazione del mondo reale che richieda l’identificazione di palindromi, non includerà quasi sicuramente quelli arbitrariamente lunghi, quindi questa risposta mostrerebbe che è ansible differenziare le impossibilità teoriche dalle applicazioni del mondo reale. Tuttavia, la regexp effettiva sarebbe piuttosto lunga, molto più lunga di un equivalente programma a 4 righe (esercizio facile per il lettore: scrivere un programma che identifichi i palindromi).

Mentre il motore PCRE supporta le espressioni regolari ricorsive (vedere la risposta di Peter Krauss ), non è ansible utilizzare una regex sul motore ICU (come ad esempio, ad esempio, Apple) per ottenere questo risultato senza codice aggiuntivo. Avrai bisogno di fare qualcosa del genere:

Questo rileva qualsiasi palindromo, ma richiede un ciclo (che sarà richiesto perché le espressioni regolari non possono contare).

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

Non è ansible. I palindromi non sono definiti da una lingua normale. (Vedi, ho imparato qualcosa nella teoria computazionale)

Con regex di Perl:

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

Sebbene, come molti hanno sottolineato, questo non può essere considerato un’espressione regolare se si vuole essere severi. Le espressioni regolari non supportano la ricorsione.

Ecco uno per rilevare i palindromi di 4 lettere (ad esempio: atto), per qualsiasi tipo di personaggio:

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

Ecco uno per rilevare i palindromi di 5 lettere (es .: radar), controllando solo le lettere:

 \([az]\)\([az]\)[az]\2\1 

Quindi sembra che abbiamo bisogno di una regex diversa per ogni lunghezza di parola ansible. Questo post su una mailing list di Python include alcuni dettagli sul perché (Finite State Automata e pumping lemma).

, puoi farlo in. Net!

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

Puoi controllare qui ! È un post meraviglioso!

A seconda di quanto sei sicuro, darei questa risposta:

Non lo farei con un’espressione regolare. Non è un uso appropriato delle espressioni regolari.

Come alcuni hanno già detto, non esiste una singola espressione regexp che rilevi un palindromo generale, ma se vuoi rilevare palindromi fino a una certa lunghezza, puoi usare qualcosa come

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

StackOverflow è pieno di risposte come “Espressioni regolari? No, non lo supportano. Non possono supportarlo.”.

La verità è che le espressioni regolari non hanno più nulla a che fare con le grammatiche regolari . Le espressioni regolari moderne presentano funzioni come i gruppi di ricorsione e bilanciamento e la disponibilità delle loro implementazioni è in continua crescita (vedi esempi di Ruby qui, ad esempio). A mio avviso, aggrapparsi alla vecchia convinzione che le espressioni regolari nel nostro campo siano tutt’altro che un concetto di programmazione è semplicemente controproducente. Invece di odiarli per la scelta delle parole che non è più appropriata, è tempo per noi di accettare le cose e andare avanti.

Ecco una citazione di Larry Wall , il creatore di Perl stesso:

(…) in generale hanno a che fare con ciò che chiamiamo “espressioni regolari”, che sono solo marginalmente legate alle vere espressioni regolari. Tuttavia, il termine è cresciuto con le capacità dei nostri motori di abbinamento, quindi non tenterò di combattere qui la necessità linguistica. Tuttavia, generalmente li chiamerò “regex” (o “regexen”, quando sono di umore anglosassone).

Ed ecco un post sul blog di uno degli sviluppatori principali di PHP :

Dato che l’articolo era piuttosto lungo, ecco un riassunto dei punti principali:

  • Le “espressioni regolari” usate dai programmatori hanno molto poco in comune con la nozione originale di regolarità nel contesto della teoria del linguaggio formale.
  • Le espressioni regolari (almeno PCRE) possono corrispondere a tutte le lingue senza contesto. In quanto tali, possono anche abbinare un HTML ben formato e praticamente tutti gli altri linguaggi di programmazione.
  • Le espressioni regolari possono corrispondere almeno ad alcune lingue sensibili al contesto.
  • La corrispondenza delle espressioni regolari è NP-completa. In quanto tale, puoi risolvere qualsiasi altro problema NP usando le espressioni regolari.

Detto questo, puoi confrontare i palindromi con espressioni regolari usando questo:

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

… che ovviamente non ha nulla a che fare con le grammatiche regolari.
Maggiori informazioni qui: http://www.regular-expressions.info/balancing.html

Nel ruby ​​è ansible utilizzare i gruppi di cattura denominati. quindi qualcosa del genere funzionerà –

 def palindrome?(string) $1 if string =~ /\A(?

| \w | (?: (?\w) \g

\k ))\z/x end

provalo, funziona …

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

Ora può essere fatto in Perl. Utilizzando il riferimento ricorsivo:

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

modificato sulla base dell’ultima parte http://perldoc.perl.org/perlretut.html

 /\A(?|.|(?:(?.)\g\k))\z/ 

è valido per il motore Oniguruma (che è usato in Ruby)

preso da Pragmatic Bookshelf

In realtà è più semplice farlo con la manipolazione delle stringhe piuttosto che con le espressioni regolari:

 bool isPalindrome(String s1) { String s2 = s1.reverse; return s2 == s1; } 

Mi rendo conto che questo non risponde alla domanda dell’intervista, ma potresti usarlo per mostrare come sai un modo migliore di fare un compito, e non sei la tipica “persona con un martello, che vede ogni problema come un chiodo “.

In Perl (vedi anche la risposta di 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 } 

Per quanto riguarda l’espressione PCRE (da MizardX):

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

L’hai provato? Sul mio PHP 5.3 sotto Win XP Pro fallisce: aaaba In realtà, ho modificato leggermente l’espressione, per leggere:

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

Penso che quello che sta succedendo sia che mentre i due personaggi esterni sono ancorati, i rimanenti interni non lo sono. Questa non è la risposta completa perché, mentre trasmette erroneamente “aaaba” e “aabaacaa”, fallisce correttamente su “aabaaca”.

Mi chiedo se esiste una correzione per questo, e anche, l’esempio Perl (di JF Sebastian / Zsolt) supera correttamente i miei test?

Csaba Gabor di Vienna

Ecco la mia risposta al quinto livello del Regex Golf (Un uomo, un piano). Funziona per un massimo di 7 caratteri con Regexp del browser (sto utilizzando Chrome 36.0.1985.143).

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

Eccone uno per un massimo di 9 caratteri

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

Per aumentare il numero massimo di caratteri per cui avrebbe funzionato, sostituiresti più volte .? con (?: (.).? \ n?)? .

Come sottolineato da ZCHudson , determinare se qualcosa è un palindromo non può essere fatto con una normale espressione regolare, poiché l’insieme di palindrome non è un linguaggio normale.

Non sono affatto d’ accordo con Airsource Ltd quando afferma che “non è ansible” non è il tipo di risposta che l’intervistatore sta cercando. Durante la mia intervista, vengo a questo tipo di domande quando mi trovo di fronte un buon candidato, per verificare se riesce a trovare la giusta argomentazione quando gli proponiamo di fare qualcosa di sbagliato. Non voglio assumere qualcuno che proverà a fare qualcosa nel modo sbagliato se ne conosce uno migliore.

qualcosa che puoi fare con perl: http://www.perlmonks.org/?node_id=577368

Spiegherei all’intervistatore che il linguaggio composto da palindromi non è un linguaggio normale, ma invece privo di contesto.

L’espressione regolare che corrisponderebbe a tutti i palindromi sarebbe infinita . Invece suggerirei di limitarsi a una dimensione massima dei palindromi da accettare; o se tutti i palindromi sono necessari utilizzare almeno un tipo di NDPA, o semplicemente usare la semplice tecnica di inversione / parità delle stringhe.

Il meglio che puoi fare con espressioni regex, prima di esaurire i gruppi di cattura:

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

Questo corrisponderà a tutti i palindromi fino a 19 caratteri di lunghezza.

La risoluzione programmatica per tutte le lunghezze è banale:

 str == str.reverse ? true : false 

Non ho ancora il rep per commentare inline, ma la regex fornita da MizardX e modificata da Csaba può essere ulteriormente modificata per farlo funzionare in PCRE. L’unico errore che ho trovato è la stringa single-char, ma posso verificarla separatamente.

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

Se riesci a farlo fallire su altre stringhe, per favore commenta.

 #!/usr/bin/perl use strict; use warnings; print "Enter your string: "; chop(my $a = scalar()); 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"; 

Dalla teoria degli automi è imansible abbinare un paliandolo di qualsiasi lunghezza (perché ciò richiede una quantità infinita di memoria). Ma è POSSIBILE abbinare Paliandromes di lunghezza fissa. Dì che è ansible scrivere una regex che corrisponda a tutti i paleandromes di lunghezza < = 5 o <= 6 ecc., Ma non> = 5 ecc. Dove il limite superiore non è chiaro

In Ruby puoi usare \b(?'word'(?'letter'[az])\g'word'\k'letter+0'|[az])\b per abbinare parole palindrome come a, dad, radar, racecar, and redivider . ps: questo regex corrisponde solo a parole palindromo che sono un numero dispari di lettere lunghe.

Vediamo come questa regex corrisponde al radar. Il limite della parola \ b corrisponde all’inizio della stringa. Il motore regex entra nella “parola” del gruppo di cattura. [az] corrisponde r che viene quindi memorizzato nello stack per il gruppo di cattura “lettera” al livello zero di ricorsione. Ora il motore regex inserisce la prima ricorsione della “parola” del gruppo. (? ‘letter’ [az]) corrisponde e cattura uno a livello di ricorsione uno. La regex inserisce la seconda ricorsione del gruppo “parola”. (? ‘letter’ [az]) cattura d al livello di ricorsione due. Durante le due successive ricorsioni, il gruppo cattura a e r ai livelli tre e quattro. La quinta ricorsione fallisce perché non ci sono caratteri rimasti nella stringa affinché [az] corrisponda. Il motore regex deve tornare indietro.

Il motore regex deve ora provare la seconda alternativa all’interno del gruppo “parola”. Il secondo [az] nella regex corrisponde alla r finale nella stringa. Il motore ora esce da una ricorsione di successo, risalendo di un livello fino alla terza ricorsione.

Dopo la corrispondenza (e parola) il motore raggiunge \ k’letter + 0 ‘. Il backreference fallisce perché il motore regex ha già raggiunto la fine della stringa dell’object. Quindi torna indietro di nuovo. La seconda alternativa ora corrisponde alla a. Il motore regex esce dalla terza ricorsione.

Il motore regex ha di nuovo abbinato (& word) e ha bisogno di tentare nuovamente il backreference. Il backreference specifica +0 o il livello attuale di ricorsione, che è 2. A questo livello, il gruppo che cattura corrisponde a d. Il backreference fallisce perché il carattere successivo nella stringa è r. Backtracking di nuovo, la seconda alternativa corrisponde a d.

Ora, \ k’letter + 0 ‘corrisponde al secondo a nella stringa. Questo perché il motore regex è tornato alla prima ricorsione durante la quale il gruppo di cattura ha eguagliato il primo a. Il motore regex esce dalla prima ricorsione.

Il motore regex è ora tornato fuori da ogni ricorsione. Che questo livello, il gruppo catturante memorizzato r. Il backreference può ora corrispondere alla r finale nella stringa. Poiché il motore non è più in alcuna ricorsione, procede con il resto della regex dopo il gruppo. \ b corrisponde alla fine della stringa. La fine della regex viene raggiunta e il radar viene restituito come corrispondenza generale.

ecco il codice PL / SQL che indica se la stringa data è palindrome o non usa le espressioni regolari:

 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; 

Le espressioni regolari ricorsive possono farlo!

Algoritmo così semplice e evidente per rilevare una stringa che contiene un palindromo:

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

Su rexegg.com/regex-recursion il tutorial spiega come funziona.


Funziona bene con qualsiasi linguaggio, qui un esempio adattato dalla stessa fonte (link) come proof-of-concept, 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"; } 

uscite

 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 

confrontando

L’espressione regolare ^((\w)(?:(?1)|\w?)\2)$ fa lo stesso lavoro, ma come sì / non invece “contiene”.
PS: sta usando una definizione dove “o” non è un palimbromo, il formato hyphened “able-elba” non è un palindromo, ma “ableelba” lo è. Chiamandolo definizione1 .
Quando “o” e “able-elba” sono palindroni, definizione di denominazione2.

Confrontando con un altro “reindirizzamento del palindromo”,

  • ^((.)(?:(?1)|.?)\2)$ la base-regex precedente senza \w restriction, accettando “able-elba”.

  • ^((.)(?1)?\2|.)$ ( @LilDevil ) Usa definizione2 (accetta “o” e “able-elba” quindi differisce anche nel riconoscimento delle stringhe “aaaaa” e “bbbb”).

  • ^((.)(?1)\2|.?)$ ( @Markus ) non rilevato “kook” né “bbbb”

  • ^((.)(?1)*\2|.?)$ ( @Csaba ) Usa definizione2 .


NOTA: per confrontare puoi aggiungere più parole a $subjects e una riga per ogni regex confrontata,

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

Una leggera raffinatezza del metodo di Airsource Ltd, in pseudocodice:

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

Puoi anche farlo senza ricorrere alla ricorsione:

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

o per escludere la stringa vuota:

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

Funziona con Perl, PCRE, Ruby, Java

dimostrazione

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

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

Corrisponde a palindromi di 5 lettere come refer e kayak. Lo fa usando una corrispondenza (non avara) di tre lettere, seguita dalla 2a e dalla 1a corrispondenza.

Collega al sito regex101 usando questo