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