Algoritmia; ejercicio de paréntesis válidos

A continuación, resolveré con Typescript el típico ejercicio de validación de paréntesis que suele ser muy usado en entrevistas de trabajo para desarrollador de software.

Planteamiento del problema

El problema a resolver, es que dado un string de paréntesis debemos evaluar si es válido.

Los caracteres de paréntesis serán:

( ) { } [ ] 

Un string de paréntesis será válido, siempre que para un paréntesis de apertura exista su respectivo paréntesis de cierre, por ejemplo:

( ( [ ] { [ ( ) [ ] ] } ) ) será válido.

( { ] } ] ) no será válido

Este ejercicio puede ser usado para validar los paréntesis en una fórmula matemática (6+2)∗(1-8)/(2+9).

También puede ser usada en los IDEs de programación, en cómo evaluan si faltan o sobran paréntesis de cierre o a cómo colorean cada paréntesis de apertura con el mismo color a su paréntesis de cierre.

Planteamiento de la solución

Como siempre, antes de ponernos a programar, te recomiendo que escribas el algoritmo que resolverá el problema y a continuación lo programas.

Se me ocurren distintas formas de solucionarlo, buscar un núcleo y eliminarlo del string. Cuando me refiero a un núcleo, me refiero a una pareja de paréntesis juntos.

Iremos eliminando núcleos hasta que ocurra una de las siguientes dos opciones:

• Hasta que el string quede vacío, con lo que el string dado como problemas es correcto
• Hasta que no existan más núcleos y el string siga teniendo caracteres, con lo que el string dado como problema no será correcto.

Sin embargo, sería más eficiente usar una pila o stack para resolver este problema.

Una pila (stack en inglés) es una lista ordenada o estructura de datos que permite almacenar y recuperar datos, siendo el modo de acceso a sus elementos de tipo LIFO (del inglés Last In, First Out, «último en entrar, primero en salir»).

El algoritmo usando una pila sería:

1. Vamos recorriendo el string
2. Comprobamos si el carácter en el que nos encontramos es de cierre o de apertura.
3. Si es un carácter de apertura guardamos su carácter de cierre en la pila.
4. Si es un carácter de cierre lo comparamos con el último valor de la pila.
5. Si son iguales, continuo, si son diferente el string dado no es válido.

Veamos un ejemplo para validar el algoritmo, usemos el string

( [ ] } } ] )

1. El primer carácter es (, como es un carácter de apertura guardo (push) en la pila su carácter de cierre, es decir, ). La pila es )
2. El siguiente carácter es [, como es un carácter de apertura guardo en la pila (push) su carácter de cierre, es decir, ]. La pila ahora es ), ]
3. El siguiente carácter es ], como es un carácter de cierre saco el último carácter de la pila (pop) y lo comparo, como ] es igual a ] continuo con el algoritmo. La pila ahora es ).
4. El siguiente carácter es ], como es un carácter de cierre saco el último carácter de la pila (pop) y lo comparo, como ] no es igual a ) salgo del algoritmo diciendo que el string no es válido

Parece que el algoritmo funciona, vamos a programarlo

A programar

Usaré para la pila un array

Para definir las parejas de paréntesis lo haré con una tabla de hash

            export function parentesisValidos(cadena: string): boolean {
              const pila: string[] = [];
              const hashParentesis: any = {
                "(": ")",
                "{": "}",
                "[": "]",
              };
            
              let resultado: boolean = true;
            
              for(let char of cadena){
                  if (!isValidChar(char)) return false;
            
                  //Busca en la tabla de hash el paréntesis de cierre del char
                  const parentesisCierre = hashParentesis[char];
              
                  if (parentesisCierre) {
                    pila.push(parentesisCierre);
                  } else {
                    //Es un paréntesis de cierre, así que lo comparo con el último de la pila
                    const lastPilaValue = pila.pop();
                    if (char !== lastPilaValue) {
                      //Si el paréntesis de cierre no es igual al char analizado, la cadena no es válida
                      resultado = false;
                      return false;
                    }
                  }
              }  
              
              return resultado;
            }
            
            function isValidChar(char: string): boolean {
              if (
                char === "{" ||
                char === "}" ||
                char === "(" ||
                char === ")" ||
                char === "[" ||
                char === "]"
              )
                return true;
              return false;
            }
          

Puedes probar el algoritmo cambiando la cadena, es el ejemplo usado en el código el resultado será true, es decir, la cadena evaluada es válida.

Hasta luego 🖖