DEV Community: Josué Isai Hernández Sánchez

Validador de Paréntesis

Josué Isai Hernández Sánchez — Thu, 09 Mar 2023 02:29:26 +0000

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.

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.

https://github.com/josueisaihs/PythonPractice

Flippind Matrix

Josué Isai Hernández Sánchez — Wed, 01 Mar 2023 22:19:40 +0000

Introducción

He de admitir que llegar a la solución final me llevó más tiempo de análisis, que de código. El problema Flipping Matrix, enuncia lo siguiente:

Sean inventó un juego que involucra una matriz donde cada celda de la matriz contiene un número entero. Puede invertir cualquiera de sus filas o columnas cualquier número de veces. El objetivo del juego es maximizar la suma de los elementos en la submatriz ubicada en el cuadrante superior izquierdo de la matriz.
Dadas las configuraciones iniciales de las matrices, ayude a Sean a invertir las filas y columnas de cada matriz de la mejor manera posible para que la suma de los elementos en el cuadrante superior izquierdo de la matriz sea máxima.

Básicamente, el problema consiste en encontrar el valor máximo de cada submatriz. Esta submatriz está delimitada por un de tamaño “nxn” y los números posibles son aquellos que se encuentran en las posiciones inversas de esa submatriz, tanto en filas como en columnas.

Solución Inicial

La solución propuesta utiliza solo dos bucles para recorrer todas las filas y columnas dentro del cuadrado morado y una función que identifica el número máximo entre las cuatro posiciones posibles para cada submatriz. La función compara el valor del cuadrado superior izquierdo, superior derecho, inferior izquierdo e inferior derecho y devuelve el valor máximo de los cuatro.

def flippingMatrix(matrix):
    n = len(matrix)//2
    max_total = 0
    for i in range(n):
        for j in range(n):
            top_left = matrix[i][j]
            top_right = matrix[i][n*2-1-j]
            bottom_left = matrix[n*2-1-i][j]
            bottom_right = matrix[n*2-1-i][n*2-1-j]
            max_val = max(top_left, top_right, bottom_left, bottom_right)
            max_total += max_val
    return max_total

El código proporcionado implementa una función llamada flippingMatrix que toma una matriz cuadrada de números y devuelve el valor máximo que se puede obtener al hacer "flip" de los valores de una submatriz de 2x2 en la matriz original. El "flip" significa cambiar los valores de la submatriz con sus correspondientes simétricos en la matriz. A continuación, explico línea a línea al algoritmo:

n = len(matrix)//2 - Calcula la mitad de la longitud de la matriz y la asigna a la variable n. Esto se utiliza más adelante para delimitar la submatriz 2x2 que se utiliza para hacer el "flip".
max_total = 0 - Inicializa la variable max_total a cero. Esta variable se utiliza para almacenar la suma del valor máximo de cada submatriz 2x2 que se considera.
for i in range(n): - Comienza un bucle que se ejecuta n veces. Este bucle itera sobre las filas de la submatriz 2x2.
for j in range(n): - Dentro del bucle anterior, comienza otro bucle que se ejecuta n veces. Este bucle itera sobre las columnas de la submatriz 2x2.
top_left = matrix[i][j] - Calcula el valor del elemento en la esquina superior izquierda de la submatriz 2x2 y lo asigna a la variable top_left.
top_right = matrix[i][n*2-1-j] - Calcula el valor del elemento en la esquina superior derecha de la submatriz 2x2 y lo asigna a la variable top_right.
bottom_left = matrix[n*2-1-i][j] - Calcula el valor del elemento en la esquina inferior izquierda de la submatriz 2x2 y lo asigna a la variable bottom_left.
bottom_right = matrix[n*2-1-i][n*2-1-j] - Calcula el valor del elemento en la esquina inferior derecha de la submatriz 2x2 y lo asigna a la variable bottom_right.
max_val = max(top_left, top_right, bottom_left, bottom_right) - Calcula el valor máximo entre los cuatro valores de la submatriz 2x2 y lo asigna a la variable max_val.
max_total += max_val - Añade el valor máximo de la submatriz 2x2 a la variable max_total.
return max_total - Devuelve el valor total máximo obtenido al hacer "flip" de los valores de una submatriz de 2x2 en la matriz original.

Conclusiones

En resumen, el código implementa una solución eficiente para el problema de “flip” de una matriz 2D y utiliza la función
max para obtener el valor máximo de una submatriz de 2x2 en cada iteración del bucle anidado.

Recomendación

En mi arículo explico como optimizar la solución 1.

Y en mi GitHub podrás descargar el código y las pruebas, además de ver soluciones a otros problemas.