Validador de Paréntesis
Tags: programming, python, algorithms, beginners
Published: 2023-03-09 02:29:26

En este artículo presentaré mi propuesta de implementación de un algoritmo para verificar si una cadena de caracteres que contiene diversos tipos de brackets (paréntesis, llaves y corchetes cuadrados) está bien formada o no. El algoritmo usa una pila para verificar si los corchetes están balanceados o no.

El método principal se llama sentinel y toma una cadena de caracteres que contiene los corchetes como argumento. La clase BracketSentinel define tres métodos principales:


```
class BracketSentinel:
    def __init__(self, *args, **kargs):
        pass
    
    def isOpen(self, bracket):
        pass

     def closeCorrectly(self, lastOpenBracket, bracketClose):
        pass

    def run(self, brackets):
        pass

    def sentinel(self, brackets, showError = False):
        pass
```

El método __init__() es el constructor de la clase y se utiliza para inicializar la lista de corchetes. La lista de corchetes se define como un diccionario con dos claves: "open" y "close". La clave "open" contiene una tupla de caracteres que representan los corchetes de apertura, mientras que la clave "close" contiene otro diccionario que mapea cada corchete de apertura a su respectivo corchete de cierre.
 

```
def __init__(self, *args, **kwargs):
        super(BracketSentinel, self).__init__(*args, **kwargs)
        self.brackets = {
            "open": ("(", "{", "["),
            "close": {
                "(": ")",
                "[": "]",
                "{": "}"
            }
        }
```

El método isOpen(self, bracket) verifica si el corchete pasado como argumento es un corchete de apertura o no. Devuelve True si el corchete es un corchete de apertura y False en caso contrario.


```
def isOpen(self, bracket):
        return bracket in self.brackets["open"]
```

Por otro parte, el método closeCorrectly(self, lastOpenBracket, bracketClose) verifica si el último corchete abierto en la pila tiene un corchete de cierre correcto o no. Toma como argumentos el último corchete abierto y el corchete de cierre que se está evaluando en la cadena de caracteres. Devuelve True si el corchete de cierre es correcto y False en caso contrario.


```
 def closeCorrectly(self, lastOpenBracket, bracketClose):
        return bracketClose == self.brackets["close"][lastOpenBracket]
```

El método run(self, brackets) es el núcleo del algoritmo de verificación de corchetes. Toma una cadena de caracteres que contiene corchetes como argumento y devuelve True si los corchetes están balanceados y False en caso contrario. El método utiliza una pila para verificar si los corchetes están balanceados. Recorre la cadena de caracteres de izquierda a derecha y agrega cada corchete de apertura a la pila. Si encuentra un corchete de cierre, verifica si el último corchete abierto en la pila tiene el corchete de cierre correcto o no. Si el corchete de cierre es correcto, elimina el último corchete abierto de la pila. Si la pila no está vacía al final del recorrido, significa que los corchetes no están balanceados y devuelve False. Si la pila está vacía al final del recorrido, significa que los corchetes están balanceados y devuelve True.

```
def run(self, brackets):
        stack = []
        for bracket in brackets:
            if self.isOpen(bracket):
                stack.append(bracket)
            elif stack.__len__() > 0 and self.closeCorrectly(stack[-1], bracket):
                del stack[-1]
            else:
                return False
        else:
            return stack.__len__() == 0
```

El método sentinel(self, brackets, showError = False) es una extensión del método run(self, brackets). Además de verificar si los corchetes están balanceados, este método también marca los corchetes que están mal formados. Si encuentra un corchete mal formado, lo marca con un "^" debajo del corchete en la cadena de caracteres y agrega el índice del corchete mal formado a la lista de errores. Al final, devuelve True si los corchetes están balanceados y False en caso contrario. Si el parámetro opcional showError se establece en True, muestra la cadena de caracteres de entrada con los corchetes mal formados marcados con un “^” debajo del corchete correspondiente.

```
def sentinel(self, brackets, showError = False):
        sintaxSuccessfull = True
        errors = []
        stack = []
        for index, bracket in enumerate(brackets):
            if self.isOpen(bracket):
                stack.append(bracket)
            elif stack.__len__() > 0 and self.closeCorrectly(stack[-1], bracket):
                del stack[-1]
            else:
                sintaxSuccessfull = sintaxSuccessfull and False
                errors.append(index)
        else:
            sintaxSuccessfull = sintaxSuccessfull and stack.__len__() == 0

        y = list(" " * brackets.__len__())
        for i in errors:
            y[i] = "^"
        print("\n", *list(brackets), "\n", *y)
        return sintaxSuccessfull
```

Finalmente, la clase BracketSentinel define un algoritmo para verificar si una cadena de caracteres que contiene corchetes está bien formada o no. El algoritmo utiliza una pila para verificar si los corchetes están balanceados. El método sentinel es una extensión del método principal run que también marca los corchetes mal formados en la cadena de caracteres de entrada.

{% embed 
https://gist.github.com/josueisaihs/f3096423a189b0a2428d7cf448141397 %}


Pruebas Unitarias
El código muestra cómo se pueden implementar pruebas unitarias en Python utilizando el módulo unittest para comprobar la funcionalidad de una clase que verifica si una cadena de corchetes está bien formada.

{% embed https://gist.github.com/josueisaihs/520c854c210a594e067db5a660acecdf %}
https://github.com/josueisaihs/PythonPractice