Вопросы Теги

Как это регулярное выражение Java обнаруживает палиндромы?

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

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

Однако механизм регулярных выражений Java поддерживает ни одна из этих «продвинутых» функций. И все же "кто-то" ( * wink * ) удалось написать следующее регулярное выражение, которое, похоже, отлично справляется со своей задачей ( см. Также на 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));
        }
    }
}

Итак кажется, это работает, но как?

Ссылки

ОБЩИЕ СМЫСЛЫ !!!

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

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

Связанные вопросы

21
задан Community 23 May 2017 в 12:32
поделиться