Это третья часть в серии образовательных регулярных выражений. СледуетКак это регулярное выражение находит треугольные числа? (где впервые вводятся вложенные ссылки) иКак мы можем сопоставить ^ n b ^ n с регулярным выражением Java? (где механизм «подсчета» прогнозируется более подробно). В этой части представлена ​​особая форма вложенного утверждения, которое в сочетании с вложенными ссылками позволяет регулярному выражению Java соответствовать тому, что большинство людей считает «невозможным»: палиндромы !!

Язык палиндромов нерегулярный; это на самом делеконтекстно-независимый (для данного алфавита). Тем не менее, современная реализация регулярных выражений распознает не только обычные языки, а рекурсивные шаблоны Perl / PCRE и группы балансировки .NET могут легко распознавать палиндромы (см .:Смежные вопросы).

Однако движок Java regex не поддерживает ни одну из этих «расширенных» функций. И все же "кто-то"(* Подмигивание *) удалось написать следующее регулярное выражение, которое, кажется, делает работу просто отлично (смотрите также на ideone.com):

public class Palindrome {
    // asserts that the entirety of the string matches the given pattern
    static String assertEntirety(String pattern) {
        return "(?<=(?=^pattern$).*)".replace("pattern", pattern);
    }

    public static void main(String[] args) {
        final String PALINDROME =
            "(?x) | (?:(.) add)+ chk"
                .replace("add", assertEntirety(".*? (\\1 \\2?)"))
                .replace("chk", assertEntirety("\\2"));

        System.out.println(PALINDROME);
        // (?x) | (?:(.) (?<=(?=^.*? (\1 \2?)$).*))+ (?<=(?=^\2$).*)

        String[] tests = {
            "",     // true
            "x",    // true
            "xx",   // true
            "xy",   // false
            "xyx",  // true
            "xxx",  // true
            "xxyx", // false
            "racecar",                // true
            "step on no pets",        // true
            "aManaPlanaCanalPanaMa",  // true
            "this is impossible",     // FALSE!!!
        };
        for (String test : tests) {
            System.out.printf("[%s] %s%n", test, test.matches(PALINDROME));
        }
    }
}

Так что это похоже на работу, но как?

Рекомендацииjava.util.regex.Patternregular-expressions.info/Freespacing(?x), Lookarounds(?=…)/(?<=…), так далее.ОБЩИЙ СМЫСЛ ПРЕДУПРЕЖДЕНИЯ !!!

Это не лучший способ обнаружить палиндромы; егоO(N^3)в лучшем случае. Выполнение этого обнаружения на языке программирования более общего назначения является одновременно более эффективным и более простым.

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

Смежные вопросыКак проверить, что строка является палиндромом с помощью регулярных выражений? - это невозможно"! (Если не ...)Как проверить, является ли данная строка палиндромом? - решения без регулярных выражений на многих языкахКак определить, является ли число простым с регулярным выражением?