Я наткнулся на вопрос о переполнении стека, в котором спрашивается, как с помощью регулярных выражений проверить, является ли строка палиндромом. Самый популярный ответ, набравший 147 голосов, указывает на то, что это невозможно, поэтому нет смысла даже пытаться. Что ж, технически он прав для палиндромов произвольной длины, но это не значит, что мы не можем сделать палиндромы максимальной длины. В качестве примечания: есть гораздо более простые способы проверки палиндромов, например, перевернуть строку и сравнить ее с оригиналом. Так зачем беспокоиться? Для умственной задачи и отработки моих навыков регулярного выражения. Я хотел, чтобы он работал на моем любимом палиндроме: Человек, план, канал, Панама! поэтому я написал регулярное выражение, которое определяет палиндромы длиной до 22 символов, игнорируя табуляции, пробелы, запятые и кавычки. Я использую регулярное выражение в стиле JavaScript.
Вот решение
\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
Вы, наверное, думаете, что либо кошка шла по моей клавиатуре, либо это секретное заклинание для вызова Ктулху на каком-то давно забытом языке. Нет, на самом деле это действительное регулярное выражение. Не стесняйтесь проверить это с помощью regexr.com, который представляет собой отличный инструмент, позволяющий мгновенно увидеть результаты вашего регулярного выражения и объяснить, что делает каждая часть. Я расскажу, как я дошел до этого, чтобы это имело смысл.
Перво-наперво нам нужно определить, повторяется ли символ.
(.)\1
Достаточно просто. Два символа повторяются? Новая часть выделена полужирным шрифтом .
Old: (.) \1 New: (.)(.)\2\1
Хорошо, это работает только для палиндромов длиной ровно 4 символа. Мы можем заставить его работать с трехсимвольными палиндромами, если сделаем второй ретроспективный просмотр необязательным.
Old: (.)(.)\2 \1 New: (.)(.)\2?\1
Круто, теперь мы можем заставить его работать для 2-х символьных строк, сделав внутреннюю часть необязательной. (?:…) создает группу без записи.
Old: (.) (.)\2? \1 New: (.)(?:(.)\2?)?\1
Мы в ударе, давайте продлим.
Old: (.)(?:(.) \2?)?\1 New: (.)(?:(.)(?:(.)\3?)?\2)?\1
Эээ… Нам удалось обнаружить строки из 5 и 6 символов, но мы потеряли 3 строки символов. Проблема в том, что \ 2 не является необязательным, и поэтому, например, с помощью aba, когда он достигает 3-го символа, он ищет второй b char, так и не найдя. Это все еще действительный палиндром, поскольку b находится точно в середине строки. Все палиндромы нечетной длины будут иметь один неповторяющийся символ в самом центре. Мы можем это исправить. Сделаем \ 2 необязательным!
Old: (.)(?:(.)(?:(.)\3?)?\2 )?\1 New: (.)(?:(.)(?:(.)\3?)?\2?)?\1
Ура! Подождите ... теперь abca - ложное срабатывание 🤦. А теперь самое сложное. Если вы готовы принять вызов, найдите время, чтобы попытаться выяснить, как бы вы его исправить, прежде чем прокручивать страницу вниз, чтобы увидеть ответ.
Мы действительно хотели бы использовать оператор if для замены \ 2 на \ 2? только если нет \ 3, но в регулярном выражении нет операторов if ... НО, у него есть оператор ИЛИ, который мы можем использовать для получения того же результата.
Old: (.)(?:(.)(?:(.)\3?)? \2? )?\1 New: (.)(?:(.)(?:(.)\3?\2|\2?))?\1
Джекпот! Все дело в небольшом изменении. С одной стороны от ИЛИ у меня есть (.) \ 3? \ 2, что означает «если есть новый внутренний символ (или два таких же), мы должны повторить группу два», а с другой стороны сторона у нас есть \ 2?, что означает «если нет нового внутреннего символа, необязательно повторить вторую группу». Второй случай указывает на то, что мы в настоящее время находимся в самой середине палиндрома, поэтому нормально иметь только один из средних символов или их может быть два. Вот почему нам нужен ?. В противном случае должна присутствовать группа 2, чтобы это был действительный палиндром. Можем ли мы продолжить? Ага!
Old: (.)(?:(.)(?:(.) \3? \2|\2?))?\1 New: (.)(?:(.)(?:(.)(?:(.)\4?\3|\3?)\2|\2?))?\1
Отлично! Я просто заменил \ 3? на (?: (.) \ 4? \ 3 | \ 3?), что соответствует той же логике, что и раньше. Теперь мы можем продолжать заменять внутреннюю группу, чтобы создать детектор палиндрома регулярных выражений любой длины! Единственная загвоздка в том, что длина регулярного выражения также будет расти, поскольку мы не можем написать цикл внутри регулярного выражения. Давайте сделаем одну достаточно большой, чтобы уловить мое целевое предложение.
(.)(?:(.)(?:(.)(?:(.)(?:(.)(?:(.)(?:(.)(?:(.)(?:(.)(?:(.)(?:(.)\11?\10|\10?)\9|\9?)\8|\8?)\7|\7?)\6|\6?)\5|\5?)\4|\4?)\3|\3?)\2|\2?))?\1
Несмотря на то, что в регулярном выражении пробелы не игнорируются, я добавил новые строки и отступы, чтобы облегчить чтение этого беспорядка, но помните, что главное выражение - это то, что работает.
(.)(?:
(.)(?:
(.)(?:
(.)(?:
(.)(?:
(.)(?:
(.)(?:
(.)(?:
(.)(?:
(.)(?:
(.)\11?\10|\10?)
\9|\9?)
\8|\8?)
\7|\7?)
\6|\6?)
\5|\5?)
\4|\4?)
\3|\3?)
\2|\2?))?
\1
Оно работает! Теперь самая сложная часть сделана. Для победного круга давайте сделаем символ палиндрома только буквенно-цифровыми и независимыми словами. Я использую флаг без учета регистра
\b(\w)(?:(\w)(?:(\w)(?:(\w)(?:(\w)(?:(\w)(?:(\w)(?:(\w)(?:(\w)(?:(\w)(?:(\w)\11?\10|\10?)\9|\9?)\8|\8?)\7|\7?)\6|\6?)\5|\5?)\4|\4?)\3|\3?)\2|\2?))?\1\b
Я заменил каждый . на \ w и заключил выражение в \ b, чтобы внутренние части слов были исключены, как в P ана ма. Для поддержки фраз давайте заставим его игнорировать пробелы, табуляции, запятые и кавычки.
\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
Я просто вставил кучу выражений [\ t, ’] * между каждым символом вне групп захвата, чтобы эти символы могли существовать в строке без необходимости их зеркального отражения на другой стороне.
И вот оно! Миссия выполнена. Они сказали, что это невозможно! … И они были правы, конечное регулярное выражение не может определять палиндромы произвольной длины, но мы все же можем создать ограниченное выражение для удовольствия!
Ваше домашнее задание - написать функцию, которая принимает длину и выводит регулярное выражение, которое может обнаруживать палиндромы до этой длины.
