Как проверить, что строка является палиндромом с помощью регулярных выражений?

Я объяснил бы интервьюеру, что язык, состоящий из палиндромов, не является регулярным языком, но вместо этого контекстно-свободный.

регулярное выражение, которое соответствовало бы всем палиндромам, будет бесконечно . Вместо этого я предложил бы, чтобы он ограничил себя любым максимальный размер палиндромов для принятия; или если все палиндромы необходимы использование в минимуме некоторый тип NDPA или просто используют метод реверсирования/равняться простой строки.

что-то можно сделать с жемчугом: http://www.perlmonks.org/?node_id=577368

Как указано ZCHudson, определите, является ли что-то палиндромом, не может быть сделан с обычным regexp, поскольку набор палиндрома не является регулярным языком.

я полностью не соглашаюсь с Airsource Ltd , когда он говорит, что "это не possibles", не вид ответа, который ищет интервьюер. Во время моего интервью я приезжаю в этот вид вопроса, когда я сталкиваюсь с хорошим кандидатом, чтобы проверить, может ли он найти правильный аргумент, когда мы предложили ему сделать что-то не так. Я не хочу нанимать кого-то, кто попытается сделать что-то неправильный путь, если он будет знать лучший.

На самом деле легче сделать это с обработкой строк, а не регулярными выражениями:

bool isPalindrome(String s1)

{

    String s2 = s1.reverse;

    return s2 == s1;
}

я понимаю, что это действительно не отвечает на вопрос интервью, но Вы могли использовать его, чтобы показать, как Вы знаете лучший способ сделать задачу, и Вы не типичный "человек с молотком, который рассматривает каждую проблему как гвоздь".

В Perl (см. также ответ 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
}

Относительно выражения PCRE (от MizardX):

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

Вы протестировали его? На моем PHP 5.3 под XP Победы Pro это перестало работать на: aaaba На самом деле, я изменил выражение выражения немного, для чтения:

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

я думаю, что происходит, то, что, в то время как внешняя пара символов привязываются, остающиеся внутренние не. Это - не совсем целый ответ, потому что, в то время как он неправильно передает "aaaba" и "aabaacaa", он действительно перестал работать правильно на "aabaaca".

интересно, делает ли там fixup для этого, и также, пример Perl (Sebastian JF / Zsolt), проходят мои тесты правильно?

Csaba Gabor из Вены

В зависимости от того, насколько уверенный Вы, я дал бы этот ответ:

я не сделал бы этого с регулярным выражением. Это не соответствующее использование регулярных выражений.

Вот один для обнаружения палиндромов с 4 буквами (например: дело), для любого типа символа:

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

Вот один для обнаружения палиндромов с 5 буквами (например: радар), проверяя на буквы только:

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

, Таким образом, кажется, что нам нужен различный regex для каждой возможной длины слова. Это сообщение в списке рассылки Python включает некоторые детали относительно почему (Конечные автоматы и насосная лемма).

С Perl regex:

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

, Хотя, как многие указали, это нельзя считать регулярным выражением, если Вы хотите быть строгими. Регулярные выражения не поддерживает рекурсию.

Это не возможно. Палиндромы не определяются регулярным языком. (См., я, DID изучает что-то в вычислительной теории)

В то время как механизм PCRE действительно поддерживает рекурсивные регулярные выражения (см. ответ Peter Krauss ), Вы не можете использовать regex на механизм ICU (как используется, например, Apple) для достижения этого без дополнительного кода. Необходимо будет сделать что-то вроде этого:

Это обнаруживает любой палиндром, но действительно требует цикла (который будет требоваться, потому что регулярные выражения не могут рассчитать).

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

Небольшое уточнение метода Airsource Ltd в псевдокоде:

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

Как уже говорили некоторые, не существует единого регулярного выражения, которое бы сразу же обнаружило общий палиндром, но если вы хотите обнаружить палиндромы до определенной длины, вы можете использовать что-нибудь например

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

Да, вы можете сделать это в .Net!

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

Вы можете проверить это здесь! Это замечательный пост!