haskell - pilas - pila char java

Comprobando si una cadena consiste de paréntesis balanceados

Question

Escribí el siguiente programa para verificar cadenas para paréntesis balanceados:

isBalanced xs = isBalanced'' xs []
isBalanced'' [] [] = True
isBalanced'' [] _ = False
isBalanced'' (''('':xs) ys = isBalanced'' xs ('')'':ys)
isBalanced'' (''['':xs) ys = isBalanced'' xs ('']'':ys)
isBalanced'' (''{'':xs) ys = isBalanced'' xs (''}'':ys)
isBalanced'' _ [] = False
isBalanced'' (x:xs) (y:ys) = (x == y) && (isBalanced'' xs ys)

Aquí hay algunos datos de ejemplo:

positives = [
isBalanced "",
isBalanced "()",
isBalanced "[]",
isBalanced "{}",
isBalanced "([]){}[{}]"
]
negatives = [
isBalanced "(",
isBalanced "[",
isBalanced "{",
isBalanced ")",
isBalanced "]",
isBalanced "}",
isBalanced "([)]",
isBalanced "{]",
isBalanced ")("
]

Como este programa usa solo los componentes básicos de recursión explícita, me pregunté si todavía no me había dado cuenta de que existía un enfoque más corto y de más alto nivel que involucraba las instalaciones de lenguaje.

De acuerdo, destilé la siguiente solución de varias respuestas y comentarios (y mis propios pensamientos):

import Text.Parsec
grammar = many parens >> return () where
parens = choice [ between (char opening) (char closing) grammar
| [opening, closing] <- ["()", "[]", "{}"]]
isBalanced = isRight . parse (grammar >> eof) ""
isRight (Right _) = True
isRight _ = False

Answer 1

Usando un doblez izquierdo

import Data.List (foldl'')
isBalanced xs = null $ foldl'' op [] xs
where
op (''('':xs) '')'' = xs
op (''['':xs) '']'' = xs
op (''{'':xs) ''}'' = xs
op xs x = x:xs

El doblez crea una pila de caracteres encontrados anteriormente, eliminando cualquier coincidencia a medida que los encuentra. Si termina con una lista vacía, la cadena está balanceada.

Usando un doblez izquierdo en la mónada Maybe

La desventaja de usar un pliegue a la izquierda es que toda la cuerda siempre debe ser escaneada. Sería bueno abortar la operación con una falla si se encuentra una llave de cierre sin una llave de apertura correspondiente. Aquí hay una versión que hace precisamente eso.

import Control.Monad (foldM)
isBalanced'' xs = maybe False null $ foldM op [] xs
where
op (''('':xs) '')'' = Just xs
op (''['':xs) '']'' = Just xs
op (''{'':xs) ''}'' = Just xs
op xs x | x `elem` ")]}" = Nothing
| otherwise = Just (x:xs)

Answer 2

Creo que la respuesta de Hammar es la mejor, pero aquí hay pasos más pequeños que puedes hacer: usar null y lookup :

{-# LANGUAGE PatternGuards #-}
isBalanced xs = isBalanced'' xs []
isBalanced'' [] x = null x
isBalanced'' (c:xs) ys | Just d <- lookup c par = isBalanced'' xs (d:ys)
where par = [(''('','')''), (''['','']''),(''{'',''}'')]
isBalanced'' _ [] = False
isBalanced'' (x:xs) (y:ys) = x == y && isBalanced'' xs ysl

Sus datos positives y negatives ejemplo definitivamente deberían usar un map , o incluso all .

Answer 3

Probablemente exagerar por un problema así de simple, pero podrías intentar buscar los combinadores de analizadores .

Como una simplificación más elemental, puede reescribir su recursividad para doblar una función que lleva una pila y un carácter de la cadena a una nueva pila. (Sin embargo, si esto lo haría realmente más simple está en el ojo del espectador).

Answer 4

Como dijo Henning , los combinadores de analizadores funcionarían para esto. Aquí hay un ejemplo usando Parsec :

import Text.Parsec
grammar = many braces >> return ()
where braces = choice [ between (char ''('') (char '')'') grammar
, between (char ''['') (char '']'') grammar
, between (char ''{'') (char ''}'') grammar
]
isBalanced :: String -> Bool
isBalanced input = case parse (grammar >> eof) "" input of
Left _ -> False
Right _ -> True