Problema Básico de Pilas – Validación de Paréntesis

Un problema común de code-kata es la verificación de una cadena de caracteres compuesta por paréntesis la cual debe cerrar apropiadamente todos los paréntesis abiertos.

En este artículo explicamos una solución sencilla a este problema.

Enunciado del problema

Dada una cadena de caracteres «s», que contiene caracteres alfanuméricos y en particular símbolos de tres tipos de paréntesis (redondos ( ), cuadrados [ ] y corchetes { }); validemos que la cadena es válida; es decir, que cada conjunto de paréntesis abierto sea cerrado apropiadamente.

Ejemplos de cadenas válidas:

• ""
• "Hola a todos (as) este articulo será publicado en [fecha de publicación] {...texto adicional ...} "
• "((({[{[([({})])]}]})))"

Ejemplos de cadenas inválidas:

• Cierres excesivos: "Hola a todos (as) este articulo será publicado en [fecha de publicación] {...texto adicional ...})"
• Cierres Faltantes: "Hola a todos (as) este articulo será publicado en [fecha de publicación] {...texto adicional ..."
• Cierres incorrectos: "((({[{[([({})])]}]}))}"

Análisis del problema

Este es un problema típico para explicar el uso de la estructura de datos de tipo pila, la cual permite almacenar datos bajo un modelo de «último en entrar, primero en salir» mediante las siguientes funciones típica:

• push(): agrega un elemento al tope de la pila.
• peek(): muestra el elemento que está en el tope de la pila sin removerlo.
• pop(): remueve y devuelve un elemento del tope la pila.

Para solucionar este problema, en nuestro caso vamos a considerar un proceso de iteración caracter por caracter sobre la cadena de caracteres suministrada de forma que podamos tomar decisiones para cada caracter:

1. Si el caracter es un símbolo de apertura de paréntesis entonces lo agregamos a la pila denominada «paréntesis por cerrar»
2. Si el caracter es un símbolo de cerrado de paréntesis, entonces verificamos que si el último paréntesis por cerrar coincide con el paréntesis que estamos cerrando. Si ese no es el caso, establecemos que la cadena es inválida.
3. Si el caracter no es ni apertura ni cierre de paréntesis simplemente lo ignoramos y pasamos al siguiente.

Una vez terminado el escaneo de la cadena, también debemos verificar que no queden paréntesis por cerrar en la pila. Si esto se cumple entonces la cadena es válida.

Otro detalle importante de considerar es que podemos estructuras de tipo «hashmap» para determinar (1) cuáles caracteres debemos considerar como apertura de paréntesis y (2) cuáles caracteres consideramos como cerrado de paréntesis y a qué tipo de apertura corresponden.

La siguiente figura ilustra la ejecución iterativa de esta lógica para una cadena válida.

En esta descripción tenemos el caso de la cadena «(({{[[randomtext]]}}))» la cual posee 22 caracteres, se abren dos paréntesis redondos, dos corchetes y dos cuadrados, luego se continua con los caracteres de randomtext y finalmente se cierran adecuadamente dos paréntesis cuadrados, dos corchetes y dos redondos. Es una cadena válida.

Se describe de arriba a abajo un total de 22 ciclos iterativos donde se evalúa cada caracter respecto de si aparecen en las especificaciones de paréntesis abiertos (OPENSPEC) y paréntesis cerrados (CLOSESPEC). Nótese que esta última especificación también describe qué tipo de paréntesis de apertura corresponden al paréntesis de cierre. Por ejemplo para el paréntesis de cierre «)» se espera que cierre un paréntesis de tipo «(«.

Cuando el paréntesis es de apertura, este se almacena en nuestra pila de paréntesis por cerrar mediante la función push()

Cuando el paréntesis es de cierre, se saca el último paréntesis por cerrar de la pila mediante la función pop(), la cual extrae el paréntesis de apertura registrado más recientemente. Entonces se verifica si el elemento proveniente de la función pop() es el mismo paréntesis de apertura que corresponde al símbolo de cierre especificado. Si no es ese el caso, la cadena es inválida.

Una vez que se ha iterado sobre toda la cadena sin encontrar ningún cierre inválido, verificamos que la pila de paréntesis por cerrar esté vacía. Si este es el caso la cadena es válida. De lo contrario la cadena es inválida.

Para el ejemplo de la figura 1, la cadena es válida.

La figura 2 a continuación muestra este mismo análisis pero para una cadena inválida «(({([[randomtext]]}}))«. La cadena en este caso es inválida porque el primer símbolo de cierre de corchetes deberia ser cierre de paréntesis redondos.

En este caso, una vez que hemos detectado que la cadena es inválida en el ciclo 19, no es necesario seguir iterando sobre la cadena suministrada.

Seguidamente, en la figura 3 describimos el caso de una cadena inválida porque no se cierran todos los paréntesis abiertos:

En este caso se itera sobre todos los caracteres de la cadena, todos los símbolos de cierre encontrados tienen un símbolo de apertura de paréntesis correspondiente en la pila, pero luego de todas las iteraciones queda un paréntesis sin cerrar en la pila.

Código en JavaScript

El siguiente listado muestra el código en Javascript.

Puedes encontrar una versión actualizada en mi paquete de npm jn-didactic la cual incluye pruebas unitarias que verifica el algoritmo en los diferentes escenarios de interés.

También puedes clonar el código fuente directamente desde GitHub:

https://github.com/janunezc/jn-didactic

/**
     * Takes a string s and scans it to determine it is valid regarding bracket closures.
     * Examples:
     * VALID: ""
     *        "({[[[{}]]]})"
     *        "(abc(def)[][])"
     * INVALID: ((
     *          ([{{{}}})    < Missing a ] before last )
     * 
     * APPROACH:
     * Fast track on empty string
     * Scan string for opening or closing bracket symbols
     *  if an opening brackt is found, add it to stack
     *  if a closing bracket is found, determine if last item in stack is the corresponding opening one.
     *   if not, return false
     * When all string is scanned, check stack is empty. If so, then return true.
     * Otherwise return false
     * 
     * openparentargets: "(,[,{"
     * closeparentargets: ")=>(,}=>{,]=>["
     * s:"([{randomtext}])"
     * p:0
     *  c:"(" //part of our openparentargets  ==> PROCESS OPENPAREN
     *   stack.push(c):"("
     * p:1
     *  c:"[" //part of our openparentargets
     *   stack.push(c)="[("
     * 
     * p:2
     *  c="{" //part of our openparentargets
     *   stack="{[("
     * 
     * p:3...12 ==> IGNORE
     *  c="r"|"a"..."randomtext" ignore all of these
     * 
     * p:13
     *  c:"}" //part of our closeparentargets => corresponding opening paren (cop): "{" ==>PROCESS CLOSEPAREN
     *   stack.pop: "{"
     *   stack: "[("
     *   cop!==pop ("{"): return false
     * 
     * p:14
     *  c:"]" //part of our closeparentargets => corresponding opening paren (cop): "["
     *   stack.pop: "["
     *   stack: "("
     *   cop!==pop ("["): return false
     * 
     * p:15
     *  c:")"
     *  //part of our closeparentargets => corresponding opening paren (cop): "("
     *   stack.pop: "("
     *   stack: ""
     * 
     * check stack is empty (peek===undefined): return true otherwise return false/
     * 
     * 
     * "({[[[{}]]]})"
     * hashmap openParenthesis
     * openP["("] = ")"
     * openP["{"] = "}"
     * openP["["] = "]"
     * 
     * closeP[")"] = "("
     * closeP["}"] = "{"
     * closeP["]"] = "["
     * let openStack
     * scanString => char:
     *   if(openP[char]){
     *     openStack.push(char); 
     *   }
     * 
     *   openCandidate = closeP[char];
     *   if(openCandidate){
     *     targetOpenP = openStack.pop()
     *     if(targetOpenP !== openCandidate) return false;
     *   }
     * 
     * @param {string} s 
     */
    function checkBracketClosures(s) {
        let openParenSpec = "({[";
        let closeParenSpec = {
            ")": "(",
            "}": "{",
            "]": "["
        }

        let stack = [];

        for (let i = 0; i < s.length; i++) {
            let myChar = s.charAt(i);
            let openSpecItem = openParenSpec.includes(myChar);
            let cop = closeParenSpec[myChar];

            if (openSpecItem) {
                stack.push(myChar);
            } else if (cop) {
                let popped = stack.pop();
                if (cop !== popped) return false;
            }
        }

        if (stack.length === 0) return true;
        else return false;

    }

 6,010 total views,  3 views today