java - solo - regular expressions

¿Es posible unir paréntesis anidados con expresiones regulares sin usar grupos de recursión o de equilibrio?

Question

StackOverflow alienta las preguntas con respuesta propia, por lo que decidí crear esta publicación para compartir algo que descubrí recientemente.

El problema : hacer coincidir un grupo de paréntesis arbitrariamente anidado en un sabor de expresiones regulares como java.util.regex de Java que no admite grupos de recursión ni de equilibrio. Es decir, unir los 3 grupos externos en:

(Primera segunda tercera)))))))

Este ejercicio es puramente académico, ya que todos sabemos que no se supone que las expresiones regulares se usen para unir estas cosas, del mismo modo que no se supone que las puntas Q se usen para limpiar los oídos.

Answer 1

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)))))))
                                ^

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

Paréntesis extra eliminado

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

Paréntesis adicionales agregados para coincidir con paréntesis de cierre adicionales

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

Capacidades de expresiones regulares

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

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

Entrada

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

(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 con estas entradas deberían arrojar los siguientes resultados:

1. NO VÁLIDO (sin coincidencia)
2. VÁLIDO (partido)
3. VÁLIDO (partido)

Código

Hay varias formas de hacer coincidir grupos anidados. Todas las soluciones proporcionadas a continuación dependen de sabores de expresiones regulares que incluyen capacidades de recursividad (por ejemplo, PCRE).

Ver expresiones regulares en uso aquí

Usando el bloque DEFINE

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

Nota : Esta expresión regular usa las banderas gmx

Sin bloque DEFINE

Ver expresiones regulares en uso aquí

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

Nota : Esta expresión regular usa las banderas gmx

Sin modificador x (una línea)

Ver expresiones regulares en uso aquí

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

Sin nombre (grupos y referencias)

Ver expresiones regulares en uso aquí

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

Nota : Este es el método más corto posible que se me ocurrió.

Explicación

Explicaré la última expresión regular, ya que es un ejemplo simplificado y mínimo de todas las otras expresiones regulares que se encuentran arriba.

• ^ Afirmar 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 número de veces
    • [^()/r/n]+ Coincide con cualquier carácter que no esté presente en el conjunto ()/r/n una o más veces
  • /( Hacer coincidir un carácter de paréntesis izquierdo / inicial ( literalmente
  • ((?1)|(?2)) Capture cualquiera de los siguientes en el grupo de captura 3
    • (?1) Recurrir el primer subpatrón (1)
    • (?2) Recurrir el segundo subpatrón (2)
  • /) Haga coincidir un carácter de paréntesis derecho / de cierre ) literalmente
  • (?3)* Repetir el tercer subpatrón (3) cualquier número de veces
• $ Posición de afirmación al final de la línea

Answer 2

¡En efecto! Es posible usar referencias directas:

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

Proof

Et voila ; ahí está. Eso justo allí coincide con un grupo completo de paréntesis anidados de principio a fin. Dos subcadenas por partido se capturan y guardan necesariamente; Estos son inútiles para usted. Solo concéntrate en los resultados del partido principal.

No, no hay límite de profundidad. No, no hay construcciones recursivas ocultas allí. Simplemente las viejas miradas, con un toque de referencia hacia adelante. Si su sabor no admite referencias directas (lo estoy mirando, JavaScript), lo siento. Realmente soy. Desearía poder ayudarte, pero no soy un maldito hacedor 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 hacer coincidir esos grupos externos es porque no se superponen. Tan pronto como los partidos que deseamos comiencen a superponerse, debemos ajustar un poco nuestra estrategia. Todavía podemos inspeccionar el tema en busca de grupos de paréntesis correctamente equilibrados. Sin embargo, en lugar de emparejarlos directamente, debemos guardarlos con un grupo de captura de esta manera:

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

Exactamente lo mismo que la expresión anterior, excepto que he envuelto la mayor parte de ella con anticipación para evitar consumir personajes, agregué un grupo de captura y modifiqué los índices de referencia para que jueguen 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 demonios funciona esto realmente?

Me alegra que lo hayas preguntado. El método general es bastante simple: iterar a través de los caracteres uno a la vez mientras simultáneamente coincide con las siguientes apariciones de ''('' y '')'', capturando el resto de la cadena en cada caso para establecer posiciones desde las cuales reanudar la búsqueda en el siguiente iteración Déjame desglosarlo pieza por pieza:

Conclusión

Entonces, ahí lo tienes. Una forma de hacer coincidir estructuras anidadas equilibradas utilizando referencias directas junto con características estándar (extendidas) de expresiones regulares: sin recursividad o 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 muchos 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 comparta mi entusiasmo por superar los límites de la posibilidad con regex, me encantaría saber de usted . Si hay interés, tengo otro material similar para publicar.