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


94

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.



2
W dzisiejszych czasach (2018) i kto szuka "wyrażenia regularnego palindromu", zobacz dyskusję na temat PCRE obsługującego wzorce rekurencyjne w łączu Prachara i mój regex regex poniżej, z porównaniami .
Peter Krauss

Odpowiedzi:


152

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


6
@SteveMoser W Rubim 1.9.x wyrażenia regularne nie są już regularnymi (w sensie teorii automatów), a zatem możliwe jest sprawdzanie palindromów. Jednak dla celów i zamiarów palindromów nie można sprawdzić za pomocą regularnego wyrażenia regularnego (czy ma sens?).

1
@SteveMoser Jest dobry writeup regularnej silnika ekspresji Ruby ( >=1.9) tutaj

@John ma rację, więc w kontekście pytania Jose ma rację, a hqt się myli.
Steve Moser

2
W kategoriach akademickich wyrażenie regularne ma określone granice (definiuje DFA). W rzeczywistości wiele silników regexp (przede wszystkim Perl i jego krewni) obsługuje odwołania wsteczne, które naruszają definicję akademicką (stają się NFA lub nawet szersze). Więc to pytanie ma różne odpowiedzi w zależności od tego, jaki był układ odniesienia pytającego.
jiggy,

W teście ustnym powinieneś iść z „formalnym to niemożliwe”, ale powinieneś zauważyć, że niektóre silniki regex na to pozwalają.
Oliver A.

46

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

4
Dobra odpowiedź. Pytanie nie dotyczyło ani jednego wyrażenia regularnego, które wykrywa palindrom prosto z pudełka - po prostu dotyczyło metody wykrywania palindromów, która wykorzystuje wyrażenia regularne. Gratuluję spojrzenia na to w ten sposób.
Stewart

1
Zobacz także najprostsze dopasowywanie (bez manipulacji na ciągach) przy użyciu tylko jednego wyrażenia regularnego, stackoverflow.com/a/48608623/287948
Peter Krauss

Dzięki @PeterKrauss. Nie wiedziałem, że PCRE ma rekurencję. Odwołaj się do swojej odpowiedzi.
Airsource Ltd

32

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


2
Większość silników wyrażeń regularnych przechwytuje więcej niż zwykłe języki (na przykład net może przechwytywać pasujące nawiasy). Tylko standardowe wyrażenia regularne są ograniczone do regularnych języków.
Santiago Palladino,

Pytanie zawierało jednak termin „wyrażenie regularne” ... więc odpowiedź ZCHudsona jest poprawna.
paxos1977

2
@austirg: Odpowiedź ZCHudson jest poprawna, ale niekompletna. Wyrażenia regularne używane we współczesnych językach programowania i wyrażenia regularne używane w teoretycznych klasach CS to różne bestie. Termin to tylko dziedzictwo historyczne. Zobacz stackoverflow.com/questions/233243#235199 i moją odpowiedź.
jfs

2
@JF Sebastian - musiałbym się w tej sprawie zgodzić z austirg. Gdy termin wyrażenie regularne jest używany bez określonego języka programowania, wówczas ma zastosowanie definicja comp sci. Nie wszystkie języki obsługujące wyrażenia regularne mogą to zrobić, więc nie powinniśmy zakładać, że ten używany tutaj tak.
Rontologist

@Rontologist: Nie widzę żadnych ograniczeń w wyborze języka programowania w pytaniu, więc każdy język jest dozwolony. Spójrz po prawej: jakie jest znaczenie wyrażenia regularnego w powiązanych pytaniach? Czy w którymś z nich jest mowa o określonym języku programowania?
jfs

27

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.


to nie działa w PCRE (nie pasuje do „ababa”), ale działa w Perlu 5.10
newacct

Masz rację. Wydaje się, że PCRE traktuje rekurencję jako grupę atomową, podczas gdy Perl pozwala na cofanie się w jej obrębie. Nie sądzę, aby można było to sprawdzić w PCRE.
Markus Jarderot

1
O dziwo, nie działa dla języków innych niż łacińskie, na przykład język ormiański.
Temujin

3
@Temujin Dzieje się tak, ponieważ znaki Unicode są dopasowywane jako zakodowane bajty (dodaj /umodyfikator ) lub z powodu znaków kombinatora. (zamiast .z \Xsekwencją wyjściową ).
Markus Jarderot,

1
Mój wzór nie działa w PCRE. Działa w Perlu. Twój wzór zawodzi, gdy podciągi są powtarzane. Na przykład abababa. Nie jest możliwe, aby działał z rekurencją dla każdego wejścia, gdy używa się silników regex opartych na PCRE. Casimirs regex używa innego podejścia, używając iteracji i stanu zmiennego, i jest dość fascynujący.
Markus Jarderot

15

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


14

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.


3
Mam nadzieję, że podasz trochę więcej wyjaśnień, aby pokazać, że naprawdę rozumiesz ograniczenia wyrażenia regularnego. Twoja prosta odpowiedź może zostać odebrana jako „Jestem zaskoczony”.
Scott Wegner

Stąd klauzula zależności, którą podał.
Will Bickford

13

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

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

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


Cały sens Regex o smaku .NET polega na tym, że nie są one regularne, ponieważ nie są automatami skończonymi; tak naprawdę nie są wyrażeniami regularnymi w sensie teoretycznym.
kot

12

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


9

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


6

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 

1
Nazwane grupy przechwytywania nie są ściśle wyrażeniami regularnymi. willamette.edu/~fruehr/LLC/lab5.html
Steve Moser

2
Masz rację. Właśnie dlatego wskazałem, że należałoby używać nazwanych grup przechwytywania.
Taylor

Czy ktoś mógłby przypadkiem wyjaśnić, że RE charakter po znaku nowicjuszowi? Rozumiem wszystkie następujące kwestie (przecinki oddzielają atomy) /, \ A, (, |, \ w, |, (, (, \ w,),),), \ z, /, x, ale nie nie rozumiesz żadnego z nich? <p>,?:,? <l>, \ g <p>, \ k <l + 0> i używam rubular.com do pomocy i wygląda na to, że rozumiem RE ( naturalnie), ale to mi nie pomaga, a nawet „Kompletny przewodnik po wyrażeniach regularnych w Ruby znajduje się w Kilofie”. nie pomaga, ponieważ strona połączona z „Kilofem” nie wyjaśnia atomów, których nie rozumiem. Wiem ? PODĄŻAJĄC ZA dopasowaniem Zero lub jednym z a, ale? poprzedzający znak?
Kevin Ford, łódź podwodna,

Ach, nazwane grupy przechwytywania ! Ładny. @SteveMoser to teraz uszkodzony link, ale znalazłem inny . Dzięki Taylor za wspomnienie o nich, ponieważ w przeciwnym razie nie miałbym pojęcia, co oznacza? <p> i? <l> i?: (Grupa przechwytująca bez przechwytywania) oraz \ g <p> i \ k <l + 0>. Nadal nie widzę czego? <p> | jest chociaż. Nie | znaczy „lub”? Nie mogę znaleźć dokumentacji tego użycia rury w RE. Nadal z przyjemnością zobaczę szczegółowe wyjaśnienie tego bardzo ładnego RE.
Kevin Ford, łódź podwodna,

5

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ź . ”


Chociaż bardzo podoba mi się ta odpowiedź, myślę, że dostaniesz dodatkowe punkty, używając BreakIterator do prawidłowego podzielenia ciągu na znaki wizualne.
Trejkaz

5

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


1
Udało mi się to z nieco mniejszą liczbą znaków, ^ (.) (.) (.)?.? \ 3 \ 2 \ 1 $
Ben Ellis

Dziękuję bardzo za zepsucie mi tego :-)
U10-Napastnik

Dlaczego reszta ludzi ma 13, ale to jest 19
U10-Forward

5

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

5

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


1
To bardzo interesująca odpowiedź na pytanie regex. Właściwie jedyny wzór, który przeszedł niektóre z moich testów . Dzięki za to jeden Casimir :)
bobble bubble

1
@bobblebubble: Dziękuję za wsparcie. Jak widać, ostatnio zredagowałem tę odpowiedź, ponieważ poprzednia wersja była błędna (przez trzy lata, co za wstyd).
Casimir et Hippolyte

4

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



3

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
}

2

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.



2

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.


2

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

Twoje wyrażenie regularne nie działa. Na przykład wskaże, że „abac” to dopasowanie ...
Darwin Airola

2

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.


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

2

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


2

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.


2

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;

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

2
Chociaż ten kod może odpowiedzieć na pytanie, dostarczenie dodatkowego kontekstu dotyczącego tego, jak i / lub dlaczego rozwiązuje problem, poprawiłoby długoterminową wartość odpowiedzi.
Kaczor Donald

2

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


0

Drobne udoskonalenie metody Airsource Ltd w pseudokodzie:

WHILE string.length > 1
    IF /(.)(.*)\1/ matches string
        string = \2
    ELSE
        REJECT
ACCEPT
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.