Esta es la tercera parte de una serie de artículos educativos sobre expresiones regulares. Sigue¿Cómo esta expresión regular encuentra números triangulares? (donde las referencias anidadas se introducen por primera vez) y¿Cómo podemos unir a ^ n b ^ n con Java regex? (donde el mecanismo de "conteo" anticipado se desarrolla más a fondo). Esta parte presenta una forma específica de afirmación anidada, que cuando se combina con referencias anidadas permite que la expresión regular de Java coincida con lo que la mayoría de la gente cree que es "imposible": ¡palíndromos!

El lenguaje de los palíndromos es noregular; en realidad essin contexto (para un alfabeto dado). Dicho esto, la implementación moderna de expresiones regulares reconoce más que solo los lenguajes regulares, y los patrones recursivos de Perl / PCRE y los grupos de equilibrio de .NET pueden reconocer fácilmente los palíndromos (ver:preguntas relacionadas)

Sin embargo, el motor regex de Java no admite ninguna de estas características "avanzadas". Y sin embargo, "alguien"(*guiño*) logró escribir la siguiente expresión regular que parece hacer el trabajo bien (ver también en 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));
        }
    }
}

Entonces esto parece funcionar, pero ¿cómo?

Referenciasjava.util.regex.Patternregular-expressions.info/Freespacing(?x), Lookarounds(?=…)/(?<=…)etc.¡ALERTA DE SENTIDO COMÚN!

Esta no es la mejor manera de detectar palíndromos; susO(N^3)a lo mejor. Realizar esta detección en un lenguaje de programación de propósito más general es más eficiente y más directo.

No querríasutilizar regex para detectar palíndromos por las mismas razones por las que no querríasutilizar regex para encontrar números primos. Dicho eso, lo haríasestudiar cómo una expresión regular de grupo no recursiva y sin equilibrio puede detectar palíndromos por las mismas razones que ustedestudiar cómo se puede usar una expresión regular para las pruebas de primalidad: es divertido, es desafiante, es educativo.

Preguntas relacionadas¿Cómo verificar que una cadena es un palíndromo usando expresiones regulares? - es imposible"! (a no ser que...)¿Cómo verificar si la cadena dada es palíndromo? - soluciones que no son expresiones regulares en muchos idiomas¿Cómo determinar si un número es primo con regex?