TecNoticias, tu portal de información

Verifique la forma correcta de una cadena que contiene paréntesis de apertura y cierre usando solo SQL

Validar si una cadena contiene paréntesis equilibrados es un problema práctico que resulta del análisis/validación de cadenas/expresiones en varios escenarios prácticos. En este artículo, analizamos cómo validar una cadena de este tipo que solo contiene paréntesis abiertos ‘(‘ y cerrados ‘)’ usando solo SQL declarativo.Foto de Elena Mozhvilo en UnsplashArtículo anterior: Subsecuencia creciente más larga de una matriz en SQL Dada una cadena que contiene solo paréntesis abiertos y cerrados, ¿puede determinar si estos paréntesis están equilibrados? Estar equilibrado significa: Cada paréntesis de apertura ‘(‘ tiene exactamente un paréntesis de cierre ‘)’ después de él. Un paréntesis de cierre ‘)’ siempre se corresponde con exactamente un paréntesis de apertura ‘(‘ que aparece antes. Los siguientes son ejemplos de válido cadenas de paréntesis equilibradas:((()()))()()()()(()()(()())) Los siguientes son ejemplos de inválido paréntesis equilibrado:((()( — aquí, los primeros 2 y el último paréntesis abierto no tienen un paréntesis de cierre coincidente()()()()) — aquí, el último paréntesis de cierre no coincide con ningún otro paréntesis no coincidente abrir paréntesisLa tabla de entrada tiene 2 columnas:idx: El índice de problemas. es decir, la primera cadena a comprobar tendrá idx = 1, la segunda cadena a comprobar tendrá idx = 2, y así sucesivamente.padres: Una cadena que contiene solo paréntesis de apertura y cierre. Se debe verificar que esta cadena esté bien formada. CREAR entradas de TABLA (IDX SERIAL PRIMARY KEY, parens TEXT NOT NULL); INSERT INTO input (parens) VALORES
(‘((()()))’), (‘((()(‘), (‘()()()())’), (‘()()()()’), (‘(()()(()()))’);SELECT * FROM entradas;La tabla de entrada para el problema del paréntesis balanceado (Imagen del autor) En los lenguajes de programación imperativos, este problema generalmente se resuelve manteniendo una pila que recibe un ‘(‘ cada vez que se encuentra en la cadena de entrada. Por lo tanto, la pila contiene solo ‘ (‘ caracteres. Cada vez que se ve un ‘)’ en la entrada, se compara con un ‘(‘ en la parte superior de la pila, y el carácter ‘)’ se elimina. Dado que tenemos solo un tipo de corchetes abiertos (y cerrados)podemos eliminar la pila y mantener solo un contadorque cuenta cuántos caracteres ‘(‘ no coincidentes se han visto hasta ahora. Cada vez que se encuentra un carácter ‘(‘, incrementamos el contador, y cada vez que se encuentra un carácter ‘)’, disminuimos el contador.Valor de contador negativo: Si el contador alguna vez alcanza un valor negativo (Valor final del contador: Después de procesar todos los caracteres de la cadena de entrada, si el valor del contador es != 0, indica un problema. Un valor positivo indica un carácter ‘(‘ no coincidente en la entrada, y un valor negativo ya se consideró anteriormente. El código SQL para esta solución se ve así: CON as_split AS (
— Primero divida cada cadena de entrada de modo que cada carácter esté en su
— Fila propia. Nos aseguramos de etiquetar cada fila de entrada con el original
— índice de la cadena de entrada de la que proviene para que sepamos cuál
— problema del que es parte.
SELECCIONE
idx,
DESANIDADO(
STRING_TO_ARRAY(
padres, NULL
)
) como cap
DESDE entradas
), con_anotación AS (
— Anotar caracteres de cada problema (índice único) con su
— posición usando ROW_NUMBER(). También anote un paréntesis abierto con
— +1 y paréntesis cercano con un número -1, para que podamos mantener
— una suma corriente de estos contadores más adelante.
SELECCIONE
idx,
ch,
ROW_NUMBER() SOBRE(PARTICIÓN POR idx) COMO row_num,
CASO CUANDO ch = ‘(‘ ENTONCES +1 DE LO CONTRARIO -1 FIN COMO ctr
DESDE as_split
), con_running_sum AS (
— Encuentra la suma acumulada de los caracteres en cada problema. Tenga en cuenta que estamos
— resolviendo todos los problemas a la vez (piense en “API por lotes”) en lugar de alimentar
— introduciendo cada problema una vez en la máquina de solución.
SELECCIONE
idx,
ch,
ctr,
núm_fila,
SUM(ctr) SOBRE(PARTICIÓN POR idx ORDEN POR row_num ASC) COMO running_sum,
MAX(núm_fila) SOBRE(PARTICIÓN POR idx) COMO máx_núm_fila
DESDE con_anotación
),con_resultado AS (
— El resultado es válido solo si nunca alcanzamos una suma acumulada negativa
— (lo que indica que tenemos un pariente más cercano que un pariente correspondiente
— paréntesis abierto) y si terminamos con una suma acumulada de 0. Si terminamos con un
— ejecutando suma > 0 entonces tenemos un paréntesis abierto adicional que no es
— emparejado con un paréntesis cercano correspondiente.
SELECCIONE
idx,
CASO CUANDO MIN(running_sum) CASO CUANDO SUMA(
CASO CUANDO fila_num = max_fila_num ENTONCES suma_ejecutable ELSE 0 FIN
) = 0 ENTONCES VERDADERO DE LO CONTRARIO FALSO FIN COMO termina_con_suma_cero
DESDE with_running_sum
GRUPO POR 1
)SELECCIONE
lhs.idx,
rhs.parens,
CASO
CUANDO tiene_negativo O NO termina_con_suma_cero ENTONCES FALSO
ELSE VERDADERO FIN
AS is_valid_parens
DESDE with_result lhs INNER JOIN entradas rhs
ON lhs.idx = rhs.idx
ORDER BY lhs.idx ASC; Hay bastantes tablas intermedias utilizadas en la solución anterior para facilitar la lectura y para separar los distintos pasos de procesamiento. Esta es la primera vez que usamos la palabra clave UNNEST en SQL. Esta es también la primera vez que escribo una solución que procesa por lotes múltiples entradas y las resuelve a la vez. aprovecho el idx campo que indica el índice de la cadena de entrada. Todas las mesas intermedias utilizan el idx campo para separar soluciones a diferentes problemas.El resultado de la solución O(n) (Imagen del autor)Costo estimado: El costo estimado para esta consulta en una tabla con 5 filas de entrada distintas es 45k. La mayor parte de este costo parece provenir del uso de las funciones de agregación de ventanas. Si bien he etiquetado el tiempo de ejecución para que sea Sobre), dependería de cómo el motor de la base de datos ejecute internamente la consulta. Por ejemplo, si el motor nota que la asignación de la núm_fila columna usando NUMERO DE FILA() da como resultado filas que tienen un valor estrictamente creciente para esa columna, y la base de datos puede conservar ese orden de fila en las tablas CTE, luego puede evitar hacer una clasificación más adelante cuando encuentra un ORDENAR POR cláusula en la ejecución de la función de ventana aquí. SUM(ctr) OVER(PARTITION BY idx ORDER BY row_num ASC) AS running_sum,The ORDENAR POR en el SOBRE() La cláusula anterior es esencial para garantizar que obtengamos una suma acumulada y no una suma total para toda la partición.