¿Cómo podemos unir a^nb^n?

La respuesta es, no hace falta decirlo, ¡ SÍ! Seguramente puedes escribir un patrón de expresiones regulares de Java que coincida con a ⁿ b ⁿ . Utiliza una anticipación positiva para la afirmación y una referencia anidada para "contar".

En lugar de dar el patrón inmediatamente, esta respuesta guiará a los lectores a través del proceso de derivarlo. Se dan varias sugerencias a medida que se construye lentamente la solución. En este aspecto, es de esperar que esta respuesta contenga mucho más que otro patrón de expresiones regulares. Con suerte, los lectores también aprenderán cómo "pensar en expresiones regulares" y cómo unir armoniosamente varias construcciones, para que puedan derivar más patrones por sí mismos en el futuro.

El lenguaje utilizado para desarrollar la solución será PHP por su concisión. La prueba final una vez finalizado el patrón se realizará en Java.

Paso 1: anticipación de la afirmación

Comencemos con un problema más simple: queremos hacer coincidir a+el comienzo de una cadena, pero solo si va seguida inmediatamente por b+. Podemos usar ^para anclar nuestra coincidencia y, dado que solo queremos hacer coincidir a+sin b+, podemos usar la aserción de anticipación(?=…) .

Aquí está nuestro patrón con un sencillo arnés de prueba:

function testAll($r, $tests) {
   foreach ($tests as $test) {
      $isMatch = preg_match($r, $test, $groups);
      $groupsJoined = join('|', $groups);
      print("$test $isMatch $groupsJoined\n");
   }
}
 
$tests = array('aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb');
 
$r1 = '/^a+(?=b+)/';
#          └────┘
#         lookahead

testAll($r1, $tests);

El resultado es ( como se ve en ideone.com ):

aaa 0
aaab 1 aaa
aaaxb 0
xaaab 0
b 0
abbb 1 a

Este es exactamente el resultado que queremos: hacemos coincidir a+, solo si está al principio de la cadena y solo si va seguido inmediatamente de b+.

Lección : Puedes usar patrones en búsquedas para hacer afirmaciones.

Paso 2: Capturar con anticipación (y modo de espaciado libre)

Ahora digamos que aunque no queremos que b+sea parte del partido, queremos capturarlo de todos modos en el grupo 1. Además, como anticipamos tener un patrón más complicado, usemos xun modificador para el espacio libre para que puede hacer que nuestra expresión regular sea más legible.

Basándonos en nuestro fragmento de PHP anterior, ahora tenemos el siguiente patrón:

$r2 = '/ ^ a+ (?= (b+) ) /x';
#             │   └──┘ │
#             │     1  │
#             └────────┘
#              lookahead
 
testAll($r2, $tests);

El resultado ahora es ( como se ve en ideone.com ):

aaa 0
aaab 1 aaa|b
aaaxb 0
xaaab 0
b 0
abbb 1 a|bbb

Tenga en cuenta que, por ejemplo, aaa|bes el resultado de join-ing con lo que capturó cada grupo '|'. En este caso, el grupo 0 (es decir, lo que coincidía con el patrón) capturó aaay el grupo 1 capturó b.

Lección : Puedes capturar dentro de un vistazo. Puede utilizar espacios libres para mejorar la legibilidad.

Paso 3: refactorizar la anticipación en el "bucle"

Antes de que podamos introducir nuestro mecanismo de conteo, debemos hacer una modificación a nuestro patrón. Actualmente, la anticipación está fuera del +"bucle" de repetición. Esto está bien hasta ahora porque solo queríamos afirmar que hay un b+siguiente nuestro a+, pero lo que realmente queremos hacer eventualmente es afirmar que para cada uno de alos que coincidimos dentro del "bucle", hay un correspondiente bque lo acompaña.

No nos preocupemos por el mecanismo de conteo por ahora y simplemente hagamos la refactorización de la siguiente manera:

• Primera refactorización a+a (?: a )+(tenga en cuenta que (?:…)es un grupo que no captura)
• Luego mueva la búsqueda hacia adelante dentro de este grupo que no captura
  • Tenga en cuenta que ahora debemos "saltar" a*antes de poder "ver" el patrón b+, así que modifique el patrón en consecuencia.

Entonces ahora tenemos lo siguiente:

$r3 = '/ ^ (?: a (?= a* (b+) ) )+ /x';
#          │     │      └──┘ │ │
#          │     │        1  │ │
#          │     └───────────┘ │
#          │       lookahead   │
#          └───────────────────┘
#           non-capturing group

El resultado es el mismo que antes ( como se ve en ideone.com ), por lo que no hay cambios en ese sentido. Lo importante es que ahora estamos haciendo la afirmación en cada iteración del +"bucle". Con nuestro patrón actual, esto no es necesario, pero a continuación haremos que el grupo 1 "cuente" para nosotros usando la autorreferencia.

Lección : Puedes capturar dentro de un grupo que no captura. Las búsquedas se pueden repetir.

Paso 4: Este es el paso donde comenzamos a contar.

Esto es lo que vamos a hacer: reescribiremos el grupo 1 de modo que:

• Al final de la primera iteración de +, cuando la primera acoincide, debería capturarb
• Al final de la segunda iteración, cuando otra acoincide, debería capturarbb
• Al final de la tercera iteración, debería capturarbbb
• ...
• Al final de la n -ésima iteración, el grupo 1 debería capturar b ⁿ
• Si no hay suficientes bpara capturar en el grupo 1, entonces la afirmación simplemente falla

Entonces el grupo 1, que ahora es (b+), tendrá que reescribirse en algo como (\1 b). Es decir, intentamos "agregar" a ba lo que el grupo 1 capturó en la iteración anterior.

Aquí hay un pequeño problema porque a este patrón le falta el "caso base", es decir, el caso en el que puede coincidir sin la autorreferencia. Se requiere un caso base porque el grupo 1 comienza "sin inicializar"; aún no ha capturado nada (ni siquiera una cadena vacía), por lo que un intento de autorreferencia siempre fallará.

Hay muchas maneras de solucionar esto, pero por ahora hagamos que la coincidencia de autorreferencia sea opcional , es decir \1?. Esto puede funcionar perfectamente o no, pero veamos qué hace, y si hay algún problema, cruzaremos ese puente cuando lleguemos a ello. Además, agregaremos algunos casos de prueba más mientras estamos en ello.

$tests = array(
  'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb'
);
 
$r4 = '/ ^ (?: a (?= a* (\1? b) ) )+ /x';
#          │     │      └─────┘ | │
#          │     │         1    | │
#          │     └──────────────┘ │
#          │         lookahead    │
#          └──────────────────────┘
#             non-capturing group

El resultado ahora es ( como se ve en ideone.com ):

aaa 0
aaab 1 aaa|b        # (*gasp!*)
aaaxb 0
xaaab 0
b 0
abbb 1 a|b          # yes!
aabb 1 aa|bb        # YES!!
aaabbbbb 1 aaa|bbb  # YESS!!!
aaaaabbb 1 aaaaa|bb # NOOOOOoooooo....

¡Ajá! ¡Parece que ahora estamos muy cerca de la solución! ¡Logramos que el grupo 1 "cuente" usando la autorreferencia! Pero espera... ¡¡algo anda mal con el segundo y último caso de prueba!! ¡No hay suficientes bs y de alguna manera contó mal! Examinaremos por qué sucedió esto en el siguiente paso.

Lección : Una forma de "inicializar" un grupo de autorreferencia es hacer que la coincidencia de autorreferencia sea opcional.

Paso 4½: comprender qué salió mal

El problema es que dado que hicimos que la coincidencia de autorreferencia sea opcional, el "contador" puede "restablecerse" a 0 cuando no hay suficientes b. Examinemos de cerca lo que sucede en cada iteración de nuestro patrón como aaaaabbbentrada.

 a a a a a b b b
↑
# Initial state: Group 1 is "uninitialized".
           _
 a a a a a b b b
  ↑
  # 1st iteration: Group 1 couldn't match \1 since it was "uninitialized",
  #                  so it matched and captured just b
           ___
 a a a a a b b b
    ↑
    # 2nd iteration: Group 1 matched \1b and captured bb
           _____
 a a a a a b b b
      ↑
      # 3rd iteration: Group 1 matched \1b and captured bbb
           _
 a a a a a b b b
        ↑
        # 4th iteration: Group 1 could still match \1, but not \1b,
        #  (!!!)           so it matched and captured just b
           ___
 a a a a a b b b
          ↑
          # 5th iteration: Group 1 matched \1b and captured bb
          #
          # No more a, + "loop" terminates

¡Ajá! En nuestra cuarta iteración, todavía pudimos igualar \1, ¡pero no pudimos igualar \1b! Dado que permitimos que la coincidencia de autorreferencia sea opcional con \1?, el motor retrocede y tomó la opción "no, gracias", que luego nos permite hacer coincidir y capturar solo b!

Sin embargo, tenga en cuenta que, excepto en la primera iteración, siempre puede hacer coincidir solo la autorreferencia \1. Esto es obvio, por supuesto, ya que es lo que acabamos de capturar en nuestra iteración anterior, y en nuestra configuración siempre podemos igualarlo nuevamente (por ejemplo, si capturamos la bbbúltima vez, tenemos la garantía de que todavía habrá bbb, pero puede haber o puede que no sea bbbbesta vez).

Lección : Cuidado con retroceder. El motor de expresiones regulares retrocederá tanto como usted lo permita hasta que el patrón dado coincida. Esto puede afectar el rendimiento (es decir, un retroceso catastrófico ) y/o la corrección.

Paso 5: ¡El dominio de sí mismo al rescate!

La "solución" ahora debería ser obvia: combinar la repetición opcional con un cuantificador posesivo . Es decir, en lugar de simplemente ?, use ?+en lugar (recuerde que una repetición que se cuantifica como posesiva no retrocede, incluso si dicha "cooperación" puede resultar en una coincidencia del patrón general).

En términos muy informales, esto es lo ?+que ?dice ??:

?+

• (opcional) "No tiene por qué estar ahí".
  • (posesivo) "¡pero si está ahí, debes tomarlo y no soltarlo!"

?

• (opcional) "No tiene por qué estar ahí".
  • (codicioso) "pero si es así, puedes tomarlo por ahora".
    • (retrocediendo) "¡pero es posible que te pidan que lo dejes pasar más tarde!"

??

• (opcional) "No tiene por qué estar ahí".
  • (reacio) "e incluso si lo es, no tienes que tomarlo todavía".
    • (retrocediendo) "¡pero es posible que le pidan que lo tome más tarde!"

En nuestra configuración, \1no estará allí la primera vez, pero siempre estará allí en cualquier momento posterior, y siempre queremos igualarlo en ese momento. Por lo tanto, \1?+lograríamos exactamente lo que queremos.

$r5 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ /x';
#          │     │      └──────┘ │ │
#          │     │          1    │ │
#          │     └───────────────┘ │
#          │         lookahead     │
#          └───────────────────────┘
#             non-capturing group

Ahora el resultado es ( como se ve en ideone.com ):

aaa 0
aaab 1 a|b          # Yay! Fixed!
aaaxb 0
xaaab 0
b 0
abbb 1 a|b
aabb 1 aa|bb
aaabbbbb 1 aaa|bbb
aaaaabbb 1 aaa|bbb  # Hurrahh!!!

¡¡¡Voilá!!! ¡¡¡Problema resuelto!!! ¡Ahora estamos contando correctamente, exactamente como queremos!

Lección : Aprenda la diferencia entre repetición codiciosa, renuente y posesiva. Opcional-posesivo puede ser una combinación poderosa.

Paso 6: toques finales

Entonces, lo que tenemos ahora es un patrón que coincide arepetidamente, y por cada acoincidencia, hay un correspondiente bcapturado en el grupo 1. +Termina cuando no hay más a, o si la aserción falló porque no hay un bfor correspondiente. un a.

Para finalizar el trabajo, simplemente necesitamos agregar a nuestro patrón \1 $. Esta es ahora una referencia inversa a lo que coincidió con el grupo 1, seguida del ancla del final de la línea. El ancla garantiza que no haya ningún extra ben la cadena; en otras palabras, que en realidad tenemos a ⁿ b ⁿ .

Aquí está el patrón finalizado, con casos de prueba adicionales, incluido uno de 10.000 caracteres:

$tests = array(
  'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb',
  '', 'ab', 'abb', 'aab', 'aaaabb', 'aaabbb', 'bbbaaa', 'ababab', 'abc',
  str_repeat('a', 5000).str_repeat('b', 5000)
);
 
$r6 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ \1 $ /x';
#          │     │      └──────┘ │ │
#          │     │          1    │ │
#          │     └───────────────┘ │
#          │         lookahead     │
#          └───────────────────────┘
#             non-capturing group

Encuentra 4 coincidencias: ab, aabb, aaabbby a ⁵⁰⁰⁰ b ⁵⁰⁰⁰ . Solo se necesitan 0,06 segundos para ejecutarse en ideone.com .

Paso 7: la prueba de Java

Entonces el patrón funciona en PHP, pero el objetivo final es escribir un patrón que funcione en Java.

public static void main(String[] args) {
 
        String aNbN = "(?x) (?:  a  (?= a* (\\1?+ b))  )+ \\1";
        String[] tests = {
                "",      // false
                "ab",    // true
                "abb",   // false
                "aab",   // false
                "aabb",  // true
                "abab",  // false
                "abc",   // false
                repeat('a', 5000) + repeat('b', 4999), // false
                repeat('a', 5000) + repeat('b', 5000), // true
                repeat('a', 5000) + repeat('b', 5001), // false
        };
        for (String test : tests) {
                System.out.printf("[%s]%n  %s%n%n", test, test.matches(aNbN));
        }
 
}
 
static String repeat(char ch, int n) {
        return new String(new char[n]).replace('\0', ch);
}

El patrón funciona como se esperaba ( como se ve en ideone.com ).

Y ahora llegamos a la conclusión...

Es necesario decir que tanto el a*análisis anticipado como el " +bucle principal" permiten retroceder. Se anima a los lectores a confirmar por qué esto no es un problema en términos de corrección y por qué al mismo tiempo hacer ambos posesivos también funcionaría (aunque tal vez mezclar cuantificadores posesivos obligatorios y no obligatorios en el mismo patrón pueda llevar a percepciones erróneas).

También se debe decir que si bien es bueno que haya un patrón de expresiones regulares que coincida con a ⁿ b ⁿ , esta no siempre es la "mejor" solución en la práctica. Una solución mucho mejor es simplemente hacer coincidir ^(a+)(b+)$y luego comparar la longitud de las cadenas capturadas por los grupos 1 y 2 en el lenguaje de programación anfitrión.

En PHP, puede verse así ( como se ve en ideone.com ):

function is_anbn($s) {
   return (preg_match('/^(a+)(b+)$/', $s, $groups)) &&
      (strlen($groups[1]) == strlen($groups[2]));
}

El propósito de este artículo NO es convencer a los lectores de que las expresiones regulares pueden hacer casi cualquier cosa; claramente no puede, e incluso para las cosas que puede hacer, se debe considerar al menos una delegación parcial al idioma anfitrión si eso conduce a una solución más simple.

Como se mencionó al principio, si bien este artículo está necesariamente etiquetado [regex]para stackoverflow, quizás se trate de más que eso. Si bien ciertamente es valioso aprender sobre afirmaciones, referencias anidadas, cuantificadores posesivos, etc., quizás la lección más importante aquí sea el proceso creativo mediante el cual uno puede intentar resolver problemas, la determinación y el trabajo duro que a menudo requiere cuando estás sujeto a diversas restricciones, la composición sistemática de varias partes para construir una solución funcional, etc.

¡Material extra! ¡Patrón recursivo PCRE!

Como mencionamos PHP, es necesario decir que PCRE admite patrones y subrutinas recursivos. Por lo tanto, el siguiente patrón funciona para preg_match( como se ve en ideone.com ):

$rRecursive = '/ ^ (a (?1)? b) $ /x';

Actualmente, la expresión regular de Java no admite patrones recursivos.

¡Aún más material extra! ¡ ¡Emparejando a ⁿ b ⁿ c ⁿ !!

Así que hemos visto cómo hacer coincidir a ⁿ b ⁿ que no es regular, pero aún así está libre de contexto, pero ¿podemos también hacer coincidir a ⁿ b ⁿ c ⁿ , que ni siquiera está libre de contexto?

¡La respuesta es, por supuesto, sí! Se anima a los lectores a intentar resolver este problema por su cuenta, pero la solución se proporciona a continuación (con implementación en Java en ideone.com ).

^ (?: a (?= a* (\1?+ b) b* (\2?+ c) ) )+ \1 \2 $

Sep 04 '2010 22:09 polygenelubricants