¿Es posible hacer coincidir los paréntesis nesteds con expresiones regulares sin usar grupos de recursión o balanceo?

StackOverflow fomenta las preguntas auto-respondidas, así que decidí crear esta publicación para compartir algo que descubrí recientemente.

El problema : unir un grupo de paréntesis nesteds arbitrariamente con un sabor de expresiones regulares como java.util.regex de Java que no admite recursividad ni grupos de equilibrio. Es decir, unir los 3 grupos externos en:

(Primera segunda tercera)))))))

Este ejercicio es puramente académico, ya que todos sabemos que las expresiones regulares no se deben usar para hacer coincidir estas cosas, al igual que los Q-tips no se deben usar para limpiar oídos.

¡En efecto! Es posible usar referencias avanzadas:

 (?=\()(?:(?=.*?\((?!.*?\1)(.*\)(?!.*\2).*))(?=.*?\)(?!.*?\2)(.*)).)+?.*?(?=\1)[^(]*(?=\2$) 

Prueba

Et voila ; ahí está. Eso justo allí coincide con un grupo completo de paréntesis nesteds de principio a fin. Dos subcadenas por partido son necesariamente capturadas y guardadas; estos son inútiles para ti. Solo concéntrese en los resultados del partido principal.

No, no hay límite en la profundidad. No, no hay construcciones recursivas escondidas allí. Simplemente simples vistas, con un toque de referencia hacia adelante. Si su sabor no admite referencias (lo estoy viendo a usted, JavaScript), entonces lo siento. Realmente soy. Desearía poder ayudarte, pero no soy un maldito trabajador de milagros.

Eso es genial y todo, ¡pero también quiero unir grupos internos!

OK, este es el trato. La razón por la que pudimos unir esos grupos externos es porque no se superponen. Tan pronto como las coincidencias que deseamos comiencen a superponerse, debemos modificar algo nuestra estrategia. Todavía podemos inspeccionar el tema para grupos de paréntesis correctamente equilibrados. Sin embargo, en lugar de combinarlos directamente, debemos guardarlos con un grupo de captura como ese:

 (?=\()(?=((?:(?=.*?\((?!.*?\2)(.*\)(?!.*\3).*))(?=.*?\)(?!.*?\3)(.*)).)+?.*?(?=\2)[^(]*(?=\3$))) 

Exactamente lo mismo que la expresión anterior, excepto que envolví la mayor parte de ella en una búsqueda anticipada para evitar el consumo de caracteres, agregué un grupo de captura y modifiqué los índices de retroreferencia para que jugaran bien con su nuevo amigo. Ahora la expresión coincide en la posición justo antes del siguiente grupo entre paréntesis, y la subcadena de interés se guarda como \ 1.

Entonces … ¿cómo diablos esto realmente funciona?

Me alegra que hayas preguntado. El método general es bastante simple: iterar a través de los caracteres uno a la vez, al mismo tiempo que coincide con las siguientes ocurrencias de ‘(‘ y ‘)’, capturando el rest de la cadena en cada caso para establecer posiciones desde las cuales reanudar la búsqueda en el próxima iteración. Déjame desglosarlo pieza por pieza:

desglose de expresiones regulares

Conclusión

Entonces, ahí lo tienes. Una forma de unir estructuras anidadas equilibradas utilizando referencias avanzadas junto con funciones de expresiones regulares estándar (extendidas), sin recurrencia ni grupos equilibrados. No es eficiente, y ciertamente no es bonito, pero es posible. Y nunca se ha hecho antes. Eso, para mí, es bastante emocionante.

Sé que muchas de ustedes usan expresiones regulares para lograr y ayudar a otros usuarios a realizar tareas más simples y prácticas, pero si hay alguien por ahí que comparte mi emoción por superar los límites de lo posible con expresiones regulares, me encantaría saber de usted . Si hay interés, tengo otro material similar para publicar.

Breve

Correcciones de entrada

En primer lugar, su entrada es incorrecta ya que hay un paréntesis adicional (como se muestra a continuación)

 (F(i(r(s)t))) ((S)(e)((c)(o))n)d) (((((((Third))))))) ^ 

Hacer las modificaciones apropiadas para incluir o excluir el paréntesis adicional, uno podría terminar con una de las siguientes cadenas:

Paréntesis adicional eliminado

 (F(i(r(s)t))) ((S)(e)((c)(o))n)d (((((((Third))))))) ^ 

Se agregó un paréntesis adicional para que coincida con el paréntesis de cierre adicional

 ((F(i(r(s)t))) ((S)(e)((c)(o))n)d) (((((((Third))))))) ^ 

Capacidades de Regex

En segundo lugar, esto es realmente solo posible en sabores regex que incluyen la capacidad de recursión ya que cualquier otro método no coincidirá adecuadamente con los paréntesis de apertura / cierre (como se ve en la solución del OP, coincide con el paréntesis extra de la entrada incorrecta como se indicó anteriormente )

Esto significa que para los sabores de expresiones regulares que actualmente no son compatibles con la recursión (Java, Python, JavaScript, etc.), la recursión (o los bashs de imitar la recursión) en expresiones regulares no es posible.


Entrada

Teniendo en cuenta que la entrada original no es válida, utilizaremos las siguientes entradas para probar en contra.

 (F(i(r(s)t))) ((S)(e)((c)(o))n)d) (((((((Third))))))) (F(i(r(s)t))) ((S)(e)((c)(o))n)d (((((((Third))))))) ((F(i(r(s)t))) ((S)(e)((c)(o))n)d) (((((((Third))))))) 

Las pruebas en contra de estas entradas deberían arrojar los siguientes resultados:

  1. NO VÁLIDO (no coincide)
  2. VÁLIDO (partido)
  3. VÁLIDO (partido)

Código

Hay múltiples formas de unir grupos nesteds. Las soluciones proporcionadas a continuación dependen de sabores de expresiones regulares que incluyen capacidades de recursión (por ejemplo, PCRE).

Ver regex en uso aquí

Usando el bloque DEFINE

 (?(DEFINE) (?[^()\r\n]+) (?(?&group)|(?&value)) (?(?&value)*\((?&groupVal)\)(?&groupVal)*) ) ^(?&group)$ 

Nota : Esta expresión regular usa las banderas gmx

Sin el bloque DEFINE

Ver regex en uso aquí

 ^(? (?[^()\r\n]+)* \((?(?&group)|(?&value))\) (?&groupVal)* )$ 

Nota : Esta expresión regular usa las banderas gmx

Sin x modificador (one-liner)

Ver regex en uso aquí

 ^(?(?[^()\r\n]+)*\((?(?&group)|(?&value))\)(?&groupVal)*)$ 

Sin nombre (grupos y referencias)

Ver regex en uso aquí

 ^(([^()\r\n]+)*\(((?1)|(?2))\)(?3)*)$ 

Nota : Este es el método más corto posible que podría surgir.


Explicación

Explicaré la última expresión regular, ya que es un ejemplo simplificado y mínimo de todas las demás expresiones regulares que aparecen encima.

  • ^ Poner posición al comienzo de la línea
  • (([^()\r\n]+)*\(((?1)|(?2))\)(?3)*) Capture lo siguiente en el grupo de captura 1
    • ([^()\r\n]+)* Capture lo siguiente en el grupo de captura 2 cualquier cantidad de veces
      • [^()\r\n]+ Coincide con cualquier carácter que no esté presente en el conjunto ()\r\n una o más veces
    • \( Coincidir con un carácter de paréntesis izquierdo / de apertura ( literalmente
    • ((?1)|(?2)) Capture cualquiera de los siguientes en el grupo de captura 3
      • (?1) Recurse al primer subpatrón (1)
      • (?2) Recurse al segundo subpatrón (2)
    • \) Coincide con un carácter de paréntesis de derecha / cierre ) literalmente
    • (?3)* Repetir el tercer subpatrón (3) cualquier cantidad de veces
  • $ Posición de confirmación al final de la línea