3.6. Paréntesis balanceados¶
Ahora dirigimos nuestra atención a usar pilas para resolver problemas reales de ciencias de la computación. Usted no tiene duda alguna respecto a expresiones aritméticas escritas tales como
\((5+6)*(7+8)/(4+3)\)
donde se utilizan paréntesis para ordenar la aplicación de las operaciones. También puede tener alguna experiencia de programación en un lenguaje como Lisp con instrucciones como
(defun cuadrado(n)
(* n n))
Esto define una función llamada cuadrado que devolverá el cuadrado de su argumento n. Lisp es notorio por usar muchísimos paréntesis.
En ambos ejemplos, los paréntesis deben aparecer de forma balanceada. Que los paréntesis estén balanceados significa que cada símbolo de apertura tiene un símbolo de cierre correspondiente y que los paréntesis están apropiadamente anidados. Considere las siguientes cadenas de paréntesis correctamente balanceados:
(()()()())
(((())))
(()((())()))
Compare aquéllas con las siguientes, que no están balanceadas:
((((((())
()))
(()()(()
La capacidad de diferenciar entre paréntesis que están correctamente balanceados y aquellos que están desbalanceados es una parte importante del reconocimiento de muchas estructuras de lenguajes de programación.
El reto entonces es escribir un algoritmo que lea una cadena de paréntesis de izquierda a derecha y que decida si los símbolos están balanceados. Para resolver este problema necesitamos hacer una observación importante. A medida que usted procesa los símbolos de izquierda a derecha, el paréntesis de apertura más reciente debe coincidir con el siguiente símbolo de cierre (ver la Figura 4). Además, el primer símbolo de apertura procesado podría tener que esperar hasta que aparezca el último símbolo de cierre. Los símbolos de cierre coinciden con los símbolos de apertura en el orden inverso de su aparición; ellos coinciden de adentro hacia afuera. Ésta es una pista de que las pilas se pueden usar para resolver el problema.
Una vez que usted acepta que una pila es la estructura de datos apropiada para almacenar los paréntesis, la declaración del algoritmo es sencilla. Comenzando con una pila vacía, se procesan las cadenas de paréntesis de izquierda a derecha. Si el símbolo es un paréntesis de apertura, incluirlo en la pila como señal de que el correspondiente paréntesis de cierre debe aparecer posteriormente. Si, por otro lado, un símbolo es un paréntesis de cierre, hacer una extracción de la pila. Los paréntesis continúan balanceados mientras sea posible extraer de la pila para emparejar cada símbolo de cierre. Si en cualquier momento no hay símbolo de apertura en la pila para emparejar un símbolo de cierre, la cadena no está balanceada apropiadamente. Al final de la cadena, cuando todos los símbolos hayan sido procesados, la pila debería estar vacía. El código en Python para implementar este algoritmo se muestra en el ActiveCode 1.
Esta función, verificarParentesis, asume que una clase Pila está disponible y devuelve un resultado booleano en cuanto a si la cadena de paréntesis está balanceada. Tenga en cuenta que la variable booleana balanceados se inicializa en True, ya que al principio no hay razón para suponer lo contrario. Si el símbolo actual es (, entonces éste se incluye en la pila (líneas 9-10) .Note también en la línea 15 que extraer simplemente elimina un símbolo de la pila. El valor devuelto no se utiliza ya que sabemos que debe ser un símbolo de apertura visto anteriormente. Al final (líneas 19-22), siempre y cuando la expresión esté balanceada y la pila haya sido vaciada completamente, la cadena representa una secuencia de paréntesis correctamente balanceada.