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

Это был вопрос интервью, на который я не смог ответить:

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

ps Уже есть вопрос « Как проверить, является ли данная строка палиндромом? », и он дает много ответов на разных языках, но нет ответа, который использует регулярные выражения.

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

На уроке теории вычислений вы узнали о конечных автоматах. Конечный автомат состоит из узлов и ребер. Каждое ребро помечено буквой конечного алфавита. Один или несколько узлов являются специальными «принимающими» узлами, а один узел является «стартовым» узлом. Когда каждая буква читается из данного слова, мы пересекаем данное ребро в машине. Если мы попадаем в состояние принятия, мы говорим, что машина «принимает» это слово.

Регулярное выражение всегда можно перевести в эквивалентный конечный автомат. То есть тот, который принимает и отклоняет те же слова, что и регулярное выражение (в реальном мире некоторые языки регулярных выражений допускают произвольные функции, они не учитываются).

Невозможно построить конечный автомат, который принимает все палиндромы. Доказательство опирается на тот факт, что мы можем легко построить строку, которая требует сколь угодно большого количества узлов, а именно строку

a ^ xba ^ x (например, aba, aabaa, aaabaaa, aaaabaaaa, ....)

где a ^ x - это повторение x раз. Для этого требуется как минимум x узлов, потому что, увидев 'b', мы должны отсчитать x раз, чтобы убедиться, что это палиндром.

Наконец, возвращаясь к исходному вопросу, вы можете сказать интервьюеру, что можете написать регулярное выражение, которое принимает все палиндромы, которые меньше некоторой конечной фиксированной длины. Если когда-либо существует реальное приложение, требующее идентификации палиндромов, оно почти наверняка не будет включать в себя произвольно длинные, поэтому этот ответ покажет, что вы можете отличить теоретические невозможности от реальных приложений. Тем не менее, реальное регулярное выражение будет довольно длинным, намного длиннее, чем эквивалентная 4-строчная программа (легкое упражнение для читателя: напишите программу, которая идентифицирует палиндромы).

Хотя движок PCRE поддерживает рекурсивные регулярные выражения (см. Ответ Питера Краусса ), вы не можете использовать регулярное выражение в движке ICU (используемом, например, Apple) для достижения этого без дополнительного кода. Вам нужно будет сделать что-то вроде этого:

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

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

Это невозможно. Палиндромы не определены обычным языком. (Смотрите, я ДЕЙСТВИТЕЛЬНО узнал кое-что по теории вычислений)

С регулярным выражением Perl:

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

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

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

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

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

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

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

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

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

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

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

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

StackOverflow полон ответов типа «Регулярные выражения? Нет, они его не поддерживают. Они не могут его поддерживать».

Дело в том, что регулярные выражения больше не имеют ничего общего с регулярными грамматиками . Современные регулярные выражения содержат такие функции, как рекурсия и балансирующие группы, и доступность их реализаций постоянно растет (см., Например, здесь примеры Ruby). На мой взгляд, придерживаться старого убеждения, что регулярные выражения в нашей области - это не что иное, как концепция программирования, просто контрпродуктивно. Вместо того, чтобы ненавидеть их за выбор слов, который больше не является самым подходящим, нам пора принять вещи и двигаться дальше.

Вот цитата Ларри Уолла , создателя самого Perl:

(…) Обычно имеет отношение к тому, что мы называем «регулярными выражениями», которые лишь незначительно связаны с реальными регулярными выражениями. Тем не менее, этот термин вырос вместе с возможностями наших механизмов сопоставления с образцом, поэтому я не собираюсь здесь бороться с лингвистической необходимостью. Я, однако, обычно назову их «регулярными выражениями» (или «регулярными выражениями», когда я нахожусь в англосаксонском настроении).

А вот пост в блоге на одном из основных разработчиков РНР :

Поскольку статья была довольно длинной, вот краткое изложение основных моментов:

• «Регулярные выражения», используемые программистами, имеют очень мало общего с исходным понятием регулярности в контексте теории формального языка.
• Регулярные выражения (по крайней мере, PCRE) могут соответствовать всем контекстно-свободным языкам. Таким образом, они также могут соответствовать хорошо сформированному HTML и почти всем другим языкам программирования.
• Регулярные выражения могут соответствовать по крайней мере некоторым контекстно-зависимым языкам.
• Сопоставление регулярных выражений является NP-полным. Таким образом, вы можете решить любую другую проблему NP, используя регулярные выражения.

При этом вы можете сопоставить палиндромы с регулярными выражениями, используя это:

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

... что явно не имеет ничего общего с обычными грамматиками.
Подробнее здесь: http://www.regular-expressions.info/balancing.html

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

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

Теперь это можно сделать на Perl. Использование рекурсивной ссылки:

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

изменен на основе почти последней части http://perldoc.perl.org/perlretut.html

В ruby ​​вы можете использовать именованные группы захвата. так что что-то вроде этого будет работать -

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

попробуйте, работает ...

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

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

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

чтобы разрешить одиночный символ:

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

Работает с Perl, PCRE

демо

Для Java:

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

демо

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

bool isPalindrome(String s1)

{

    String s2 = s1.reverse;

    return s2 == s1;
}

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

Вот мой ответ на 5-й уровень Regex Golf (Человек, план). Он работает до 7 символов с Regexp браузера (я использую Chrome 36.0.1985.143).

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

Вот один до 9 символов

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

Чтобы увеличить максимальное количество символов, с которыми он будет работать, вы должны неоднократно заменять .? с (?: (.).? \ n?)? .

Рекурсивные регулярные выражения могут это сделать!

Вот такой простой и очевидный алгоритм обнаружения строки, содержащей палиндром:

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

На rexegg.com/regex-recursion учебник объясняет, как это работает.

Он отлично работает с любым языком, вот пример, адаптированный из того же источника (ссылка), что и доказательство концепции, с использованием 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";
}

выходы

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

Сравнение

Регулярное выражение ^((\w)(?:(?1)|\w?)\2)$ выполняет ту же работу, но вместо этого да / не «содержит».
PS: используется определение, в котором «o» не является палимбромом, формат с дефисом «able-elba »не является палиндромом, а «ableelba» является. Называя это определение 1 .
Когда «o» и «able-elba »являются палиндронами, определение определения 2 .

Сравнивая с другими «регулярными выражениями палиндрома»,

• ^((.)(?:(?1)|.?)\2)$базовое регулярное выражение, указанное выше, без \wограничений, принимая "able-elba ".

• ^((.)(?1)?\2|.)$( @LilDevil ) Используйте определение2 (принимает «o» и «able-elba », что также отличается в распознавании строк« aaaaa »и« bbbb »).

• ^((.)(?1)\2|.?)$ ( @Markus ) не обнаружено ни "чудак", ни "bbbb"

• ^((.)(?1)*\2|.?)$( @Csaba ) Используйте определение2 .

ПРИМЕЧАНИЕ: для сравнения вы можете добавить больше слов $subjectsи строку для каждого сравниваемого регулярного выражения,

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

Что касается выражения PCRE (от MizardX):

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

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

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

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

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

Чаба Габор из Вены

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

это действительно для движка Oniguruma (который используется в Ruby)

взято с Pragmatic Bookshelf

В Perl (см. Также ответ Жолта Ботыкая ):

$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
}

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

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

кое-что, что вы можете сделать с perl: http://www.perlmonks.org/?node_id=577368

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

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

Лучшее, что вы можете сделать с регулярными выражениями, прежде чем у вас закончатся группы захвата:

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

Это будет соответствовать всем палиндромам длиной до 19 символов.

Программное решение для всех длин тривиально:

str == str.reverse ? true : false

У меня пока нет представителя для встроенных комментариев, но регулярное выражение, предоставленное MizardX и измененное Csaba, можно дополнительно изменить, чтобы оно работало в PCRE. Единственная ошибка, которую я обнаружил, - это строка с одним символом, но я могу проверить это отдельно.

/^((.)(?1)?\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";

Из теории автоматов невозможно сопоставить палиандром любой длины (потому что для этого требуется бесконечное количество памяти). Но МОЖНО сопоставить палиандромы фиксированной длины. Скажем, можно написать регулярное выражение, которое соответствует всем палиандромам длины <= 5 или <= 6 и т.д., но не> = 5 и т.д., где верхняя граница неясна

В Ruby вы можете использовать \b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z])\bдля сопоставления слов-палиндромов, таких как a, dad, radar, racecar, and redivider. ps: это регулярное выражение соответствует только словам-палиндромам, состоящим из нечетного количества букв.

Посмотрим, как это регулярное выражение соответствует радару. Граница слова \ b соответствует началу строки. Механизм регулярных выражений входит в группу захвата "word". [az] соответствует r, которое затем сохраняется в стеке для группы захвата «letter» на нулевом уровне рекурсии. Теперь механизм регулярных выражений вводит первую рекурсию группы «слово». (? 'letter' [az]) соответствует и захватывает на первом уровне рекурсии. Регулярное выражение входит во вторую рекурсию группы «слово». (? 'letter' [az]) захватывает d на втором уровне рекурсии. Во время следующих двух рекурсий группа захватывает a и r на третьем и четвертом уровнях. Пятая рекурсия завершается неудачно, потому что в строке не осталось символов для сопоставления [az]. Механизм регулярных выражений должен выполнить возврат.

Теперь обработчик регулярных выражений должен попробовать вторую альтернативу внутри группы «word». Второй [az] в регулярном выражении соответствует последнему r в строке. Теперь движок завершает успешную рекурсию, возвращаясь на один уровень вверх до третьей рекурсии.

После совпадения (& word) движок достигает \ k'letter + 0 '. Обратная ссылка не выполняется, поскольку механизм регулярных выражений уже достиг конца строки темы. Так что он снова возвращается назад. Вторая альтернатива теперь соответствует a. Механизм регулярных выражений выходит из третьей рекурсии.

Механизм регулярных выражений снова нашел совпадение (& word) и должен снова попытаться выполнить обратную ссылку. Обратная ссылка указывает +0 или текущий уровень рекурсии, который равен 2. На этом уровне группа захвата соответствует d. Обратная ссылка не выполняется, потому что следующий символ в строке - r. Снова возвращаемся, вторая альтернатива соответствует d.

Теперь \ k'letter + 0 'соответствует второму a в строке. Это потому, что механизм регулярных выражений вернулся к первой рекурсии, во время которой группа захвата соответствовала первому a. Механизм регулярных выражений завершает первую рекурсию.

Механизм регулярных выражений теперь снова вне всякой рекурсии. На этом уровне группа захвата хранит r. Теперь обратная ссылка может соответствовать последнему r в строке. Поскольку движок больше не находится внутри какой-либо рекурсии, он переходит к оставшейся части регулярного выражения после группы. \ b соответствует концу строки. Достигнут конец регулярного выражения, и радар возвращается как общее совпадение.

вот код PL / SQL, который сообщает, является ли данная строка палиндромом или нет, используя регулярные выражения:

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

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

\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

Поиграйте с ним здесь: https://regexr.com/4tmui

Небольшая доработка метода Airsource Ltd в псевдокоде:

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