Общая картина
Сначала мы рассмотрим это регулярное выражение из общего алгоритма большой картинки, а затем более подробно рассмотрим конкретные детали реализации.Регулярное выражение - это почти прямой перевод следующего кода Java:
static boolean isPalindrome(String s) {
if (s.isEmpty()) {
return true;
}
String g2 = null;
for (char ch : s.toCharArray()) {
String g1 = String.valueOf(ch);
// "add"
if (g2 != null && s.endsWith(g1 + g2)) {
g2 = g1 + g2;
} else if (s.endsWith(g1)) {
g2 = g1;
} else {
break;
}
}
return s.equals(g2); // "chk"
}
Это, очевидно, не самый простой / эффективный код Java для проверки на палиндромы, но он работает, и, что самое интересное, он почти напрямую переводимрегулярное выражение с почти однозначным отображением.Вот снова регулярное выражение, воспроизведенное здесь для удобства, аннотированное, чтобы подчеркнуть поразительное сходство:
// isEmpty _for-loop_
// ↓ / \
"(?x) | (?:(.) add)+ chk"
// \_/ ↑
// g1 loop body ___g2___
// / \
.replace("add", assertEntirety(".*? (\\1 \\2?)"))
.replace("chk", assertEntirety("\\2"));
// s.equals(g2)
Вложение : аннотированная и расширенная версия источникакод на ideone.com
(не стесняйтесь пока игнорировать детали assertEntirety: просто подумайте о нем как о механизме регулярных выражений черного ящика, который может сделать утверждение для всей строки независимо от того, где мы в данный момент находимся.)
Таким образом, основной алгоритм состоит в том, что мы пытаемся создать суффикс, подчиняющийся палиндромному ограничению, когда мы сканируем строку слева направо.Затем мы проверяем, можем ли мы построить полную строку таким способом.Если мы можем, то строка является палиндромом.Кроме того, в особом случае пустая строка является тривиальным палиндромом.
Как только алгоритм большой картинки понятен, мы можем проверить, как его реализует шаблон регулярного выражения.
Что свсе шаблоны регулярных выражений в Java String.replace?
, в конечном счете, представляют собой не что иное, как строки, то есть они могут быть получены с помощью строковых манипуляций, как любая строка.Да, мы можем даже использовать регулярное выражение для генерации шаблона регулярного выражения - своего рода мета-регулярный подход, если хотите.
Рассмотрим этот пример инициализации константы int (которая в конечном итоге содержит только число):
final int X = 604800;
final int Y = 60 * 60 * 24 * 7;
// now X == Y
Число, присвоенное X, является буквальным целым числом: мы можем ясно увидеть , что это за число.Это не относится к Y, который вместо этого использует выражение, и все же эта формула, кажется, передает идею о том, что представляет это число.Даже без правильного именования этих констант мы, тем не менее, понимаем, что Y, вероятно, представляет количество секунд в неделе, даже если мы не можем сразу узнать, что такое числовое значение.С другой стороны, с X мы точно знаем это число, но мы меньше понимаем, что оно представляет.
Использование строковых замен в фрагменте - аналогичная ситуация, но для строковых регулярных выражений,Вместо явного написания шаблона в виде одной буквенной строки, иногда систематическое и логическое вывод («формула») этого значения из более простых частей может быть гораздо более значимым.Это особенно верно для регулярных выражений, где часто важнее то, что мы понимаем, что делает шаблон, чем возможность видеть то, на что он похож как строковый литерал (который в любом случае не выглядит многообещающе, что со всеми дополнительными обратными слешами).
Для удобства здесь снова воспроизводится фрагмент фрагмента:
// the "formula"
final String PALINDROME =
"(?x) | (?:(.) add)+ chk"
.replace("add", assertEntirety(".*? (\\1 \\2?)"))
.replace("chk", assertEntirety("\\2"));
// the "value"
System.out.println(PALINDROME);
// ____add_____ chk_
// _______/ \____ _______/ \_____
// (?x) | (?:(.) (?<=(?=^.*? (\1 \2?)$).*))+ (?<=(?=^\2$).*)
// | \_/ \______/ |
// | 1 2 |
// |_______________________________|
Вне всякого сомнения, «формула» в этом случае гораздо более читаема, чем конечная строка «значение»..
Конечно, есть гораздо более изощренные способы программно сгенерировать шаблон регулярных выражений, и, безусловно, можно писать таким образом, что вместо того, чтобы подчеркивать его значение, можно запутывать, но разумное использование даже простых замен строк может все же сделатьчудо (как показано в этом примере).
Урок : рассмотрим программную генерацию шаблонов регулярных выражений.
Как работает add работа?
Конструкция (?:(.) add)+, где add - это утверждение, которое выполняет своего рода "подсчет", имеетуже подробно обсуждался в предыдущих двух частях.Однако стоит отметить две особенности:
-
(.) захватывает группу 1, что позволяет использовать обратную ссылку позже - Утверждение
assertEntirety вместо того, чтобы просто смотреть в будущее от нашего текущегопозиция - Мы обсудим это более подробно позже;просто представьте, что это способ утверждать всю строку
Шаблон, примененный к assertEntirety в add, выглядит следующим образом:
# prefix _suffix_
# ↓ / \
.*? ( \1 \2? )
# \________/ i.e. a reluctant "whatever" prefix (as short as possible)
# group 2 followed by a suffix captured into group 2
Обратите внимание, что группа 2 ссылается на себя с необязательным спецификатором, методика, уже обсуждаемая во второй части серии.Само собой разумеется, что группа 2 является нашим «счетчиком» в этом шаблоне: это суффикс, который мы будем пытаться увеличивать влево на каждой итерации «цикла».Поскольку мы выполняем итерацию для каждого (.) слева направо, мы пытаемся добавить этот же символ (используя обратную ссылку к \1) к нашему суффиксу.
Еще раз напомним перевод Java-кода вышеупомянутого шаблона, воспроизведенного здесьдля удобства:
if (g2 != null && s.endsWith(g1 + g2)) { // \2? is greedy, we try this first
g2 = g1 + g2;
} else if (s.endsWith(g1)) { // since \2? is optional, we may also try this
g2 = g1;
} else { // if there's no matching suffix, we "break" out of the "loop"
break;
}
Тот факт, что \2? является необязательным, означает несколько вещей:
- Это обеспечивает «базовый случай» для самоссылки (основная причинамы делаем это!)
- Поскольку
\2? является частью шаблона суффикса (и, следовательно, появляется позже в общем шаблоне), префиксная часть должна быть неохотной, следовательно, .*? вместо .*.Это позволяет \2? проявлять свою жадность. - «Счетчик» также может «сбрасываться» и давать «неправильный» результат
- Во второй части мы показали, как может произойти возврат
?в том же виде проблемного сброса - Мы решили проблему с помощью притяжательного квантификатора
?+, но здесь это неприменимо
Третий пункт более подробно рассматривается в следующем разделе.
Урок : Тщательно проанализируйте взаимодействия между жадными / неохотными повторениями в частях шаблона.
Смежные вопросы
Зачем нам нужна chk фаза?
Как упоминалось в предыдущем разделе, необязательный и возвращаемый \2? означает, что наш суффикс может уменьшаться при некоторомобстоятельства.Мы рассмотрим такой сценарий шаг за шагом для этого ввода:
x y x y z y x
↑
# Initial state, \2 is "uninitialized"
_
(x)y x y z y x
↑
# \1 captured x, \2 couldn't match \1\2 (since \2 is "uninitialized")
# but it could match \1 so it captured x
___
x(y)x y z y x
↑
# \1 captured y, \2 matched \1\2 and grew to capture yx
_
x y(x)y z y x
↑
# \1 captured x, \2 couldn't match \1\2,
# but it could match \1 so it shrunk to capture x (!!!)
___
x y x(y)z y x
↑
# \1 captured y, \2 matched \1\2 and grew to capture yx
_____
x y x y(z)y x
↑
# \1 captured z, \2 matched \1\2 and grew to capture zyx
_______
x y x y z(y)x
↑
# \1 captured y, \2 matched \1\2 and grew to capture yzyx
_________
x y x y z y(x)
↑
# \1 captured x, \2 matched \1\2 and grew to capture xyzyx
Мы можем изменить наш шаблон (и соответствующий код Java), чтобы пропустить фазу chk, и увидим, что это действительно то, что происходит:
// modified pattern without a chk phase; yields false positives!
final String PALINDROME_BROKEN =
"(?x) | (?:(.) add)+"
.replace("add", assertEntirety(".*? (\\1 \\2?)"));
String s = "xyxyzyx"; // NOT a palindrome!!!
Matcher m = Pattern.compile(PALINDROME_BROKEN).matcher(s);
if (m.matches()) {
System.out.println(m.group(2)); // prints "xyzyx"
}
Как объяснено, "xyxyzyx", который является NOT палиндромом, ложно сообщается как единое целое, потому что мы не проверяли, стал ли растущий суффикс в конечном итоге полной строкой(чего он явно не сделал в этом случае).Поэтому фаза chk (которая является assertEntirety шаблона \2) является абсолютной необходимостью в нашей установке.Мы должны подтвердить, что нам действительно удалось нарастить суффикс.Если это так, то у нас есть палиндром.
Урок : Тщательно проанализируйте любые возможные непреднамеренные побочные эффекты необязательного сопоставления с самообращением.
Основной курс: assertEntirety
Хотя мы можем написать шаблон регулярных выражений Java для обнаружения палиндромов, все, кроме assertEntirety, уже было рассмотрено в предыдущих частяхсериал.Единственная новая вещь - это таинственный черный ящик, этот мощный механизм, который волшебным образом позволил нам сделать то, что иначе «невозможно».
Конструкция assertEntirety основана на следующем мета-шаблоне вложенных обходных путей:
(?<=(?=^pattern$).*)
" Я могу видеть место где-то позади меня, где я могу смотреть вперед и видеть ^pattern$"
Название «lookaround» подразумевает относительность к нашему текущему положению: мы смотрим вокруг нас, возможно, впереди или сзади, с того места, где мы стоим.Таким образом, вложив взгляд в взгляд назад, мы можем метафорически «взлететь в небо» и посмотреть на всю картину.
Абстрагирование этого мета-паттерна в assertEntirety немного похоже на запись макросов подстановки предварительной обработки.Наличие вложенных поисков везде, вероятно, ухудшает читабельность и удобство сопровождения, поэтому мы инкапсулируем его в assertEntirety, что не только скрывает сложность его внутренней работы, но и дополнительно подчеркивает его семантику, давая ему подходящее имя.
Урок : Рассмотрите возможность абстрагирования мета-паттернов, чтобы скрыть сложность и передать семантику.
Приложение: Об взгляде бесконечной длины в Java
Observantчитатели заметят, что assertEntirety содержит .* в виде сзади, что делает его теоретическую максимальную длину бесконечной.Нет, Java официально не поддерживает просмотр в бесконечную длину.Да, как это было адекватно продемонстрировано, все равно работает.Официально это классифицируется как «ошибка»;но «кто-то» (* wink *) также может считать это «скрытой функцией».
Вполне возможно, что эта «ошибка» будет «исправлена» в будущем.Удаление этой скрытой функции нарушит это конкретное решение проблемы палиндрома Java regex.
Смежные вопросы