Jak sprawdzić, czy łańcuch jest palindromem, używając wyrażeń regularnych?

To było pytanie do wywiadu, na które nie mogłem odpowiedzieć:

Jak sprawdzić, czy łańcuch jest palindromem, używając wyrażeń regularnych?

ps Jest już pytanie „ Jak sprawdzić, czy podany ciąg jest palindromem? ” i daje wiele odpowiedzi w różnych językach, ale nie ma odpowiedzi, która używa wyrażeń regularnych.

Odpowiedź na to pytanie brzmi: „to niemożliwe”. Dokładniej, ankieter zastanawia się, czy zwróciłeś uwagę na zajęciach z teorii obliczeń.

Na zajęciach z teorii obliczeń nauczyłeś się o maszynach skończonych. Maszyna skończonych stanów składa się z węzłów i krawędzi. Każda krawędź jest oznaczona literą ze skończonego alfabetu. Jeden lub więcej węzłów jest specjalnymi węzłami „akceptującymi”, a jeden węzeł jest węzłem „początkowym”. W miarę odczytywania każdej litery z danego słowa przechodzimy przez daną krawędź w maszynie. Jeśli skończymy w stanie akceptującym, wówczas mówimy, że maszyna „przyjmuje” to słowo.

Wyrażenie regularne można zawsze przetłumaczyć na równoważną maszynę skończoną. To znaczy taki, który akceptuje i odrzuca te same słowa co wyrażenie regularne (w świecie rzeczywistym niektóre języki regexp dopuszczają dowolne funkcje, które się nie liczą).

Niemożliwe jest zbudowanie skończonej maszyny stanowej, która akceptuje wszystkie palindromy. Dowód opiera się na faktach, że możemy łatwo zbudować ciąg, który wymaga arbitralnie dużej liczby węzłów, a mianowicie ciąg

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

gdzie a ^ x jest powtórzeniem x razy. Wymaga to co najmniej x węzłów, ponieważ po zobaczeniu `` b '' musimy odliczyć x razy wstecz, aby upewnić się, że jest to palindrom.

Wreszcie, wracając do pierwotnego pytania, możesz powiedzieć ankieterowi, że możesz napisać wyrażenie regularne, które akceptuje wszystkie palindromy, które są mniejsze niż pewna ograniczona długość. Jeśli kiedykolwiek pojawi się aplikacja w świecie rzeczywistym, która wymaga zidentyfikowania palindromów, to prawie na pewno nie będzie ona zawierała dowolnie długich, więc ta odpowiedź wskazywałaby, że można odróżnić teoretyczne niemożliwości od aplikacji w świecie rzeczywistym. Jednak rzeczywiste wyrażenie regularne byłoby dość długie, znacznie dłuższe niż równoważny 4-wierszowy program (łatwe ćwiczenie dla czytelnika: napisz program, który identyfikuje palindromy).

Chociaż silnik PCRE obsługuje rekurencyjne wyrażenia regularne (patrz odpowiedź Petera Kraussa ), nie można użyć wyrażenia regularnego w silniku ICU (używanym na przykład przez Apple), aby osiągnąć to bez dodatkowego kodu. Musisz zrobić coś takiego:

To wykrywa każdy palindrom, ale wymaga pętli (która będzie wymagana, ponieważ wyrażenia regularne nie mogą liczyć).

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

To nie jest możliwe. Palindromy nie są definiowane przez zwykły język. (Widzisz, UCZĘ SIĘ czegoś z teorii obliczeniowej)

Z wyrażeniem regularnym Perl:

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

Chociaż, jak wielu zauważyło, nie można tego uznać za wyrażenie regularne, jeśli chcesz być ścisłe. Wyrażenia regularne nie obsługują rekursji.

Oto jeden do wykrywania 4-literowych palindromów (np .: akt) dla dowolnego typu postaci:

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

Oto jeden do wykrywania 5-literowych palindromów (np .: radar), sprawdzający tylko litery:

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

Wygląda więc na to, że potrzebujemy innego wyrażenia regularnego dla każdej możliwej długości słowa. Ten post na liście mailingowej Pythona zawiera kilka szczegółów wyjaśniających dlaczego (skończone automaty stanowe i lemat o pompowaniu).

W zależności od tego, jak bardzo jesteś pewny siebie, odpowiedziałbym:

Nie zrobiłbym tego za pomocą wyrażenia regularnego. Nie jest to właściwe użycie wyrażeń regularnych.

Tak , możesz to zrobić w .Net!

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

Możesz to sprawdzić tutaj ! To wspaniały post!

StackOverflow jest pełne odpowiedzi jak „wyrażenia regularne? Nie, one nie obsługują. Oni nie mogą go wspierać.”.

Prawda jest taka, że wyrażenia regularne nie mają już nic wspólnego z gramatyką regularną . Nowoczesne wyrażenia regularne obsługują takie funkcje, jak grupy rekurencyjne i równoważące, a dostępność ich implementacji stale rośnie (zobacz na przykład przykłady Rubiego). Moim zdaniem trzymanie się starego przekonania, że ​​wyrażenia regularne w naszej dziedzinie nie są niczym innym, jak koncepcją programistyczną, przynosi efekt przeciwny do zamierzonego. Zamiast nienawidzić ich za słowo, które nie jest już najwłaściwsze, nadszedł czas, abyśmy zaakceptowali pewne rzeczy i ruszyli dalej.

Oto cytat Larry'ego Walla , twórcy samego Perla:

(…) Generalnie mają do czynienia z tym, co nazywamy „wyrażeniami regularnymi”, które są tylko marginalnie związane z prawdziwymi wyrażeniami regularnymi. Niemniej jednak termin ten urósł wraz z możliwościami naszych silników dopasowywania wzorców, więc nie zamierzam tutaj walczyć z koniecznością językową. Ogólnie będę jednak nazywać je „wyrażeniami regularnymi” (lub „wyrażeniami regularnymi”, kiedy jestem w nastroju anglosaskim).

A oto blogu przez jednego z głównych programistów PHP za :

Ponieważ artykuł był dość długi, poniżej podsumowanie głównych punktów:

• „Wyrażenia regularne” używane przez programistów mają niewiele wspólnego z pierwotnym pojęciem regularności w kontekście formalnej teorii języka.
• Wyrażenia regularne (przynajmniej PCRE) mogą pasować do wszystkich języków bezkontekstowych. Jako takie mogą również dopasować dobrze sformułowany HTML i prawie wszystkie inne języki programowania.
• Wyrażenia regularne mogą pasować przynajmniej do niektórych języków kontekstowych.
• Dopasowywanie wyrażeń regularnych jest NP-zupełne. W związku z tym każdy inny problem NP można rozwiązać za pomocą wyrażeń regularnych.

Biorąc to pod uwagę, możesz dopasować palindromy do wyrażeń regularnych, używając tego:

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

... co oczywiście nie ma nic wspólnego ze zwykłą gramatyką.
Więcej informacji tutaj: http://www.regular-expressions.info/balancing.html

Jak kilku już powiedziało, nie ma pojedynczego wyrażenia regularnego, które wykryłoby ogólny palindrom po wyjęciu z pudełka, ale jeśli chcesz wykryć palindromy do określonej długości, możesz użyć czegoś takiego jak

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

Można to teraz zrobić w Perlu. Korzystanie z odwołań rekurencyjnych:

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

zmodyfikowany na podstawie ostatniej części http://perldoc.perl.org/perlretut.html

W Ruby możesz używać nazwanych grup przechwytywania. więc coś takiego zadziała -

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

spróbuj, to działa ...

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

W rzeczywistości łatwiej to zrobić za pomocą manipulacji na ciągach znaków niż wyrażeń regularnych:

bool isPalindrome(String s1)

{

    String s2 = s1.reverse;

    return s2 == s1;
}

Zdaję sobie sprawę, że to nie jest odpowiedzią na pytanie z wywiadu, ale możesz go użyć, aby pokazać, jak znasz lepszy sposób wykonania zadania, a nie jesteś typową osobą z młotkiem, która każdy problem postrzega jak gwóźdź . ”

Oto moja odpowiedź na 5. poziom Regex Golfa (Mężczyzna, plan). Działa dla maksymalnie 7 znaków z Regexp przeglądarki (używam Chrome 36.0.1985.143).

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

Oto jeden na maksymalnie 9 znaków

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

Aby zwiększyć maksymalną liczbę znaków, dla których działałby, musiałbyś wielokrotnie zamieniać .? z (?: (.).? \ n?)? .

Rekurencyjne wyrażenia regularne mogą to zrobić!

Tak prosty i oczywisty algorytm do wykrywania łańcucha zawierającego palindrom:

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

Na rexegg.com/regex-recursion samouczek wyjaśnia, jak to działa.

Działa dobrze z każdym językiem, tutaj przykład zaadaptowany z tego samego źródła (linku) co dowód słuszności koncepcji, używając 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";
}

wyjścia

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

Porównywanie

Wyrażenie regularne ^((\w)(?:(?1)|\w?)\2)$ wykonuje to samo zadanie, ale zamiast tego „zawiera” tak / nie.
PS: używa definicji, w której „o” nie jest palimbromem, format łączony „w stanie elba” nie jest palindromem, ale „w stanieelba” nim jest. Nazywanie tego definicja 1 .
Kiedy „o” i „zdolna-elba” są palindronami, definicja nazewnictwa2 .

W porównaniu z innymi „wyrażeniami regularnymi palindromu”,

• ^((.)(?:(?1)|.?)\2)$base-regex powyżej bez \wograniczeń, akceptując "ble-elba ".

• ^((.)(?1)?\2|.)$( @LilDevil ) Użyj definicji2 (akceptuje "o" i "zdolny-elba", więc różni się także rozpoznawaniem ciągów "aaaaa" i "bbbb").

• ^((.)(?1)\2|.?)$( @Markus ) nie wykryto „kook” ani „bbbb”

• ^((.)(?1)*\2|.?)$( @Csaba ) Użyj definicji2 .

UWAGA: aby porównać, możesz dodać więcej słów w $subjectsi wiersz dla każdego porównywanego wyrażenia regularnego,

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

Możesz to również zrobić bez rekurencji:

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

aby zezwolić na pojedynczy znak:

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

Działa z Perlem, PCRE

próbny

W przypadku języka Java:

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

próbny

Odnośnie wyrażenia PCRE (z MizardX):

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

Czy to przetestowałeś? Na moim PHP 5.3 pod Win XP Pro nie działa: aaaba Właściwie nieznacznie zmodyfikowałem wyrażenie wyrażenia, aby przeczytać:

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

Myślę, że dzieje się tak, że podczas gdy zewnętrzna para postaci jest zakotwiczona, pozostałe wewnętrzne nie. Nie jest to do końca pełna odpowiedź, ponieważ podczas gdy niepoprawnie przekazuje „aaaba” i „aabaacaa”, to zawodzi poprawnie w przypadku „aabaaca”.

Zastanawiam się, czy istnieje rozwiązanie tego problemu, a także, czy przykład Perla (autorstwa JF Sebastiana / Zsolta) przeszedł moje testy poprawnie?

Csaba Gabor z Wiednia

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

dotyczy silnika Oniguruma (który jest używany w Rubim)

wzięte z Pragmatic Bookshelf

W Perlu (patrz także odpowiedź Zsolta 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
}

Jak zauważył ZCHudson , ustalenie, czy coś jest palindromem, nie może być wykonane za pomocą zwykłego wyrażenia regularnego, ponieważ zestaw palindromów nie jest językiem regularnym.

Zupełnie nie zgadzam się z Airsource Ltd, gdy mówi, że „to niemożliwe” nie jest odpowiedzią, której szuka ankieter. Podczas rozmowy dochodzę do tego rodzaju pytania, kiedy mam do czynienia z dobrym kandydatem, żeby sprawdzić, czy potrafi znaleźć właściwy argument, gdy zaproponowaliśmy mu, żeby zrobił coś złego. Nie chcę zatrudniać kogoś, kto będzie próbował zrobić coś złego, jeśli zna lepiej.

coś, co możesz zrobić z perlem: http://www.perlmonks.org/?node_id=577368

Wyjaśniłbym ankieterowi, że język składający się z palindromów nie jest językiem zwykłym, lecz pozbawionym kontekstu.

Wyrażenie regularne pasujące do wszystkich palindromów byłoby nieskończone . Zamiast tego sugerowałbym, żeby ograniczył się do maksymalnego rozmiaru palindromów do zaakceptowania; lub jeśli potrzebne są wszystkie palindromy, użyj co najmniej jakiegoś typu NDPA lub po prostu użyj prostej techniki odwrócenia ciągów / równości.

Najlepsze, co możesz zrobić z wyrażeniami regularnymi, zanim skończą się grupy przechwytywania:

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

Spowoduje to dopasowanie wszystkich palindromów o długości do 19 znaków.

Programowe rozwiązywanie dla wszystkich długości jest trywialne:

str == str.reverse ? true : false

Nie mam jeszcze przedstawiciela, który mógłby komentować w tekście, ale wyrażenie regularne dostarczone przez MizardX i zmodyfikowane przez Csabę może być dalej modyfikowane, aby działało w PCRE. Jedyną awarią, jaką znalazłem, jest ciąg z jednym znakiem, ale mogę to przetestować osobno.

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

Jeśli możesz sprawić, że nie powiedzie się na jakimkolwiek innym łańcuchu, skomentuj.

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

Z teorii automatów niemożliwe jest dopasowanie do paliandromu dowolnej długości (ponieważ wymaga to nieskończonej ilości pamięci). Ale MOŻLIWE jest dopasowanie Paliandromów o stałej długości. Powiedzmy, że można napisać wyrażenie regularne pasujące do wszystkich paliandromów o długości <= 5 lub <= 6 itd., Ale nie> = 5 itd., Gdzie górna granica jest niejasna

W Rubim możesz użyć \b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z])\b do dopasowywania słów palindromowych, takich jak a, dad, radar, racecar, and redivider. ps: to wyrażenie regularne pasuje tylko do słów palindromu, które mają nieparzystą liczbę liter.

Zobaczmy, jak to wyrażenie regularne pasuje do radaru. Granica słowa \ b pasuje na początku ciągu. Mechanizm wyrażeń regularnych wstawia „słowo” grupy przechwytywania. [az] dopasowuje r, który jest następnie przechowywany w stosie dla przechwytywanej „litery” grupy przechwytywania na zerowym poziomie rekursji. Teraz mechanizm regex wprowadza pierwszą rekursję grupy „słowo”. (? 'letter' [az]) dopasowuje i przechwytuje a na pierwszym poziomie rekursji. Wyrażenie regularne wchodzi w drugą rekursję grupy „słowo”. (? 'letter' [az]) przechwytuje d na drugim poziomie rekurencji. Podczas następnych dwóch rekurencji grupa przechwytuje a i r na poziomach trzecim i czwartym. Piąta rekursja kończy się niepowodzeniem, ponieważ w ciągu nie ma żadnych znaków do dopasowania [az]. Silnik wyrażeń regularnych musi się cofnąć.

Silnik wyrażeń regularnych musi teraz wypróbować drugą alternatywę wewnątrz grupy „słowo”. Drugie [az] w wyrażeniu regularnym dopasowuje ostatnie r w ciągu. Silnik kończy teraz działanie po pomyślnej rekursji, przechodząc o jeden poziom w górę do trzeciej rekursji.

Po dopasowaniu (& słowo) silnik osiąga \ k'letter + 0 '. Odwołanie wsteczne nie powiodło się, ponieważ silnik wyrażenia regularnego osiągnął już koniec ciągu podmiotu. Więc znowu się cofa. Druga alternatywa pasuje teraz do a. Silnik wyrażeń regularnych kończy działanie z trzeciej rekursji.

Silnik wyrażeń regularnych ponownie dopasował (& słowo) i musi ponownie spróbować utworzyć odwołanie wsteczne. Odniesienie wsteczne określa +0 lub obecny poziom rekurencji, który wynosi 2. Na tym poziomie grupa przechwytywania dopasowała d. Odwołanie wsteczne kończy się niepowodzeniem, ponieważ następny znak w ciągu to r. Cofając się ponownie, druga alternatywa pasuje d.

Teraz \ k'letter + 0 'dopasowuje drugie a w ciągu. Dzieje się tak, ponieważ aparat wyrażeń regularnych powrócił do pierwszej rekursji, podczas której grupa przechwytywania dopasowała pierwszą a. Silnik wyrażeń regularnych kończy pierwszą rekursję.

Silnik wyrażeń regularnych jest teraz z powrotem poza wszelką rekurencją. Że na tym poziomie grupa przechwytująca zapisała r. Odwołanie wsteczne może teraz dopasować końcowe r w ciągu. Ponieważ silnik nie znajduje się już w żadnej rekursji, przechodzi do pozostałej części wyrażenia regularnego po grupie. \ b dopasowuje na końcu łańcucha. Osiągnięto koniec wyrażenia regularnego, a radar jest zwracany jako ogólne dopasowanie.

tutaj jest kod PL / SQL, który mówi, czy dany ciąg jest palindromem, czy nie, używając wyrażeń regularnych:

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

To wyrażenie regularne wykryje palindromy do 22 znaków, ignorując spacje, tabulatory, przecinki i cudzysłowy.

\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

Graj z tym tutaj: https://regexr.com/4tmui

Drobne udoskonalenie metody Airsource Ltd w pseudokodzie:

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