Resolviendo el problema de los paréntesis balanceados usando expresiones regulares

Problema de paréntesis equilibrados

Dado que este es un problema de programación tan famoso, lo más probable es que la mayoría de nosotros lo hayamos resuelto durante el curso CS101 o en otro lugar. Sin embargo, todavía insisto en que leamos una vez el enunciado del problema, antes de pasar a las siguientes secciones.

Digamos que tenemos una cadena de entrada que solo puede contener corchetes [], paréntesis () y llaves {} . Entonces, se dice que nuestra cadena de entrada está balanceada cuando cumple con dos criterios:

• LOFC ( Last Opened First Closed ) implica que el que abre último es el primero en cerrar
• LOFC tiene en cuenta que los paréntesis de apertura y cierre pertenecen al mismo par, a saber, (), [] y {}

Además, si la cadena de entrada está vacía, diríamos que está balanceada .

Muestra de datos de entrada

A continuación, echemos un vistazo a algunas cadenas de entrada de muestra y descubramos si están balanceadas o no:

 [()[]{}]{} is balanced [ ][ ]() is balanced () is balanced ))(( is not balanced {) is not balanced

Las mentes sesgadas tienen un pequeño espacio para la cabeza

Sí, sé que algunos de nosotros ya habríamos creado una imagen mental de una pila para comenzar a resolver este problema.

Sin embargo, es bueno que haya resuelto esto antes, o tal vez leyó este problema por primera vez y encontró una solución basada en la pila en muy poco tiempo. Sin embargo, le insto a que libere su cabeza por ahora , para que sus pensamientos no sean sesgados.

Solución usando Headspace

El objetivo de resolverlo con expresiones regulares es que es más intuitivo codificar , como veremos. Además, de ninguna manera quiero decir que sea un mejor enfoque en términos de la complejidad temporal del algoritmo.

Primero, revisemos el primero en la lista de entradas de muestra de la sección anterior:

 [()[]{}]{}

Ahora, tratemos de observar nuestras mentes mientras tratamos de resolverlo . Podemos ser un genio para resolverlo rápido, pero necesitamos observar este proceso de pensamiento lentamente. Además, debemos hacer todo en mente. Eso significa que debemos abstenernos de usar lápiz y papel.

Aunque no deberíamos necesitar más de 3 minutos , sin embargo, podemos tomarnos todo el tiempo que necesitemos para terminar esta actividad con satisfacción.

No tiene sentido ir más lejos a menos que pasemos algún tiempo aquí. Nadie nos juzga si somos lentos. Cuanto más lentos, mejor, pero debemos concentrarnos por completo en esta actividad para completarla en un solo tramo.

Y, cuando estemos listos, intentemos responder algunas preguntas:

• ¿Lo solucionamos de un solo tramo?
• ¿Pudimos centrarnos en patrones como (), {} y [] en la cadena?
• ¿Qué hicimos cuando detectamos los patrones equilibrados, a saber (), {}, []?

Démosle palmaditas a nuestra mente por darnos un amplio espacio mental para visualizar el proceso completo para resolverlo.

Ahora, todos podrían haber visualizado esto de manera diferente. Por ahora, permítanme exponer cómo lo visualicé.

Primero, pude detectar rápidamente los tres patrones de (), [], {} dentro del corchete cuadrado más ancho, junto con el patrón {} en el extremo derecho. Sin embargo, debo mencionar que en realidad no vi que hay un paréntesis más amplio que contiene los tres paréntesis equilibrados.

Luego, una vez que había detectado algunos patrones equilibrados, traté de concentrarme un poco más ignorando los ya descubiertos de mi vista. Como resultado, pude ver que hay un patrón de [] que contenía los patrones observados anteriormente.

Luego, sé que no había más patrones nuevos que pudiera detectar, y si ignoro todos estos patrones, entonces no tenía nada más que una cadena vacía.

Por supuesto, tuve que concentrarme más a medida que avanzaba hacia el siguiente paso.

Como dicen, una imagen vale más que mil palabras, así que traté de esbozar esta actividad más adelante, para retratar una mejor vista de todo el proceso:

Implementación usando sed

¡Ay! Lo sé. Lo sé. La ejecución es lo que nos emociona a muchos de nosotros.

A nosotros, los desarrolladores, nos gusta la acción. Ver el código en acción nos emociona. ¿no es así?

Pero, ¿ sed ?
¿En serio, sed? No Java, Python, Kotlin, Go, Haskell. ¿Ni siquiera C?

Sí, sed, lo es. 🙂

sed es una excelente herramienta para la coincidencia de patrones . De hecho, es un lenguaje de programación completo de Turing . ¡Entonces por qué no!

De todos modos, estamos siguiendo el enfoque de espacio de cabeza, y sed nos permitirá formalizar nuestros pensamientos sobre patrones en forma de código con bastante facilidad:

 :combine s/ \( \) //g s/ \{ \} //g s/ \[ \] //g t combine s/^$/balanced/p t s/.*/Unbalanced/p

Ese es todo nuestro código literalmente. Además, funciona para un flujo de entrada, no solo para una sola cadena . ¿No es maravilloso?

Aunque estoy enamorado de esta solución simple, también estoy de acuerdo, si no está familiarizado con sed, entonces estas líneas podrían ser un poco abrumadoras para usted. Entonces, déjame resumirlo para ti.

Como tal, nuestro script usa los conceptos de un bucle simple y sustitución usando expresiones regulares . Para la sustitución, utiliza la función de sustitución s , de sed con la bandera global, g para aplicar el efecto en todas las ocurrencias:

 s /regex/ replacement /g

Además, continuamos haciendo el emparejamiento de patrones y las sustituciones hasta que no podamos encontrar ninguno de los tres patrones. Nos mantenemos en el bucle usando la función de prueba t :

 t label

Para esto, anteriormente habíamos definido nuestra etiqueta llamada combine usando la función : (etiqueta) :

 : label

Debemos tener en cuenta que la función de prueba t se ramifica a la etiqueta si la última sustitución fue exitosa, de lo contrario, el flujo continúa línea por línea.

Una vez que hayamos salido del bucle, tendremos una cadena vacía para los casos balanceados o una cadena no vacía para los no balanceados.

Como resultado, usamos nuevamente la función de sustitución s , con la bandera print, p para mostrar un mensaje que dice "equilibrado" o "desequilibrado".

Pero, espera, en la penúltima línea, no usamos ninguna etiqueta para hacer bifurcaciones condicionales usando la función de prueba t :

 t

Sin la etiqueta, la función de prueba reinicia el ciclo de ejecución para la siguiente línea en el flujo de entrada. Eso también sucede cuando todos los comandos en el script han terminado de ejecutarse para el ciclo actual.

Ahora, hagamos un acto de fe y probemos esto con algunas cadenas de entrada de muestra.

¿Funciona nuestro código?

Primero, echemos un vistazo a nuestras cadenas de entrada:

 % nl input_parantheses.txt 1 [()[]{}]{} 2 [][]() 3 () 4 ))(( 5 {) 6 (()()) 7 )) 8 () 9 )()(

Finalmente, ejecutemos nuestro script y veamos el fruto de nuestro trabajo:

 % sed -E -n -f balanced_parantheses.sed input_parantheses.txt | nl 1 balanced 2 balanced 3 balanced 4 Unbalanced 5 Unbalanced 6 balanced 7 Unbalanced 8 balanced 9 Unbalanced

¡Suspiro! Podemos ver que la salida para cada línea de entrada cumple con el resultado esperado.

Conclusión

En este tutorial, confiamos en nuestras intuiciones y espacio de cabeza para llegar a una solución lo suficientemente buena para el problema de los paréntesis equilibrados . Además, probamos algunas expresiones regulares básicas al implementar la solución en sed.

Referencias

• [1] Problema de paréntesis válidos de Leetcode
• [2] Expresiones regulares
• [3] sed , editor de secuencias
• [4] nl , Utilidad de numeración de líneas