Estimados devs, en esta oportunidad les traigo un algoritmo muy conocido, su nombre original, naturalmente en Inglés, es Valid Parentheses. Así que comencemos!

Enunciado

Dada una cadena de texto que contiene sólo los siguientes caracteres: ( ) [ ] { }

Usted debe determinar si es válida o no.

Se dice que es válida si todo signo de apertura tiene su signo de cierre correctamente colocado y anidado.

No se tiene en cuenta jerarquías en los símbolos, es decir no es necesario que un paréntesis esté siempre dentro de un corchete y el corchete dentro de una llave, sólo importa que estén correctamente cerrados y anidados.

Por ejemplo:

Inténtalo tú primero, no saltes directo a la solución crack!

Algoritmo

Para resolver este ejercicio hacer lo siguiente:

• Las pilas o Stacks se prestan para este ejercicio ya que el orden importa.
• Analizaremos caracter por caracter de la cadena
• Si el caracter es de apertura, es decir ([{ entonces añadimos su respectivo cierre a una pila
• Cuando se encuentre con un caracter de cierre, entonces compara con el último elemento de la pila (si la pila no está vacía) y lo elimina, si son iguales significa que ese cierre está correctamente colocado, sino, entonces retornar error.
• Si está correctamente colocado continúa el análisis y como el último elemento de la pila ya fue eliminado entonces puede seguir haciendo las comparaciones.
• Si en la iteración se encuentra con un caracter de cierre y la pila está vacía quiere decir que la cadena es inválida.

Como notarás aquí usamos pilas, y con esto queda demostrado que aprender estructuras de datos es muy importante. En esta entrada te hablo de las estructuras de datos en .NET 😉

Código

    public bool IsValid(string s) {
        bool response = false;
        var pila = new Stack<char>();
        foreach(var caracter in s)
        {
            response = false;
            switch(caracter){
                case '(':
                    pila.Push(')');
                    break;
                case '[':
                    pila.Push(']');
                    break;
                case '{':
                    pila.Push('}');
                    break;
                default:
                    if(pila.Count > 0){
                        if(caracter == pila.Pop())
                            response = true;                    
                        else
                            return false;                    
                    }
                    else
                        return false;
                    break;
            }
        }
        return pila.Count == 0 ? response : false;
    }

Recuerda que esta entrada es de la serie de artículos Algoritmos notables, los cuales los subo a este repo, puedes visitarlo y descubrir más algoritmos 😉

Si te ha fascinado esta entrada compártela pues crack 🫡