2010-05-28 19 views
5

Necesito escribir una función par :: String -> Bool para verificar si una cadena dada con paréntesis se corresponde usando el módulo de pila.Función Haskell para verificar paréntesis que coincidan con

Ex:

par "(((()[()])))" = True 
par "((]())" = False 

Aquí está mi implementación del módulo de pila:

module Stack (Stack, 
       push, pop, top, 
       empty, isEmpty) 
    where 

data Stack a = Stk [a] 
      deriving (Show) 

push :: a -> Stack a -> Stack a 
push x (Stk xs) = Stk (x:xs) 

pop :: Stack a -> Stack a 
pop (Stk (_:xs)) = Stk xs 
pop _ = error "Stack.pop: empty stack" 


top :: Stack a -> a 
top (Stk (x:_)) = x 
top _ = error "Stack.top: empty stack" 

empty :: Stack a 
empty = Stk [] 

isEmpty :: Stack a -> Bool 
isEmpty (Stk [])= True 
isEmpty (Stk _) = False 

por eso es necesario para implementar una función par que pondría a prueba una serie de paréntesis y decir si los paréntesis en que se equilibran o no. ¿Cómo puedo hacer eso usando una pila?

+0

Y la pregunta es ...? –

+0

La pregunta es cómo escribir la función par. Solo tengo una implementación de pila aquí. – Rizo

+0

Rizo, luego explícalo en tu pregunta. –

Respuesta

6
module Parens where 

import Data.Map (Map) 
import qualified Data.Map as Map 

matchingParens :: Map Char Char 
matchingParens = Map.fromList [ 
    ('(', ')') 
    , ('{', '}') 
    , ('[', ']') 
    ] 

isOpening :: Char -> Bool 
isOpening c = maybe False (const True) $ Map.lookup c matchingParens 

type Stack a = [a] 

balanced :: String -> Bool 
balanced = balanced' [] 

balanced' :: Stack Char -> String -> Bool 
balanced' [] ""  = True 
balanced' _ ""  = False 
balanced' [] (c:cs) = balanced' [c] cs 
balanced' (o:os) (c:cs) 
    | isOpening c = balanced' (c:o:os) cs 
    | otherwise = case Map.lookup o matchingParens of 
     Nothing -> False 
     Just closing -> if closing == c 
     then balanced' os cs 
     else False 
+0

¡Muy bien! Me gusta su enfoque! – Rizo

+0

Por cierto, 'isOpening c = Map.member c matchingParens'. ¡Hoogle es tu amigo! – Phob

+0

¡Gracias !: –

4

Aquí está la respuesta:

parent' :: String -> Stack Char -> Bool 
parent' [] stk = isEmpty stk 
parent' (c:str) stk 
     | (c == '(') = parent' str (push c stk) 
     | (c == ')') = if isEmpty stk then False 
         else if top stk == '(' then parent' str (pop stk) 
         else False 



parent :: String -> Bool 
parent [] = True 
parent str = parent' str empty 
+0

Eso no funcionará para otros paréntesis como '['/']', '{', '}' etcétera y se romperá cuando se da es una cadena con otros personajes mezclados. ¡Pero definitivamente estás en el camino correcto! – yatima2975

+0

¡De hecho! Pero, este código es solo para pruebas de algoritmos. – Rizo

2

Yo soy muy novato Haskell. Aquí está mi intento, sin duda poco elegante, pero quería probar un enfoque diferente

data Stack a = Stk [a] 
     deriving (Show) 

push :: a -> Stack a -> Stack a 
push x (Stk xs) = Stk (x:xs) 

pop :: Stack a -> (Maybe a, Stack a) 
pop (Stk []) = (Nothing, Stk []) 
pop (Stk (x:xs)) = (Just x, Stk xs) 

top :: Stack a -> Maybe a 
top (Stk (x:_)) = Just x 
top _ = Nothing 

empty :: Stack a 
empty = Stk [] 

isEmpty :: Stack a -> Bool 
isEmpty (Stk [])= True 
isEmpty (Stk _) = False 


par :: String -> Maybe (Stack Char) 
par = foldl check (Just (Stk [])) 
     where check (Just stk) x 
       | x == '(' = Just (push x stk) 
       | x == ')' = case pop stk of 
            (Just '(', newStk) -> Just newStk 
            _ -> Nothing 
      check Nothing x = Nothing 


parCheck :: String -> Bool 
parCheck xs = case par xs of 
       Just stk -> isEmpty stk 
       Nothing -> False 
+0

Puede simplificar 'if isEmpty stk then True else False' to' isEmpty stk', 'x \' elem \ '" ("' to 'x == '('' y '(Just topElem, newStk) -> if topElem == '(' then Just newStk else Nothing; (Nothing, _) -> Nothing' to '(Just '(', newStk) -> Just newStk; _ -> Nothing'. – sdcvvc

+0

Gracias por las sugerencias .. . :) –

1
parent :: String -> Bool 
parent "" = True 
parent str = verify str empty 

verify :: String -> Stack Char -> Bool 
verify [] stk = isEmpty stk 
verify (c:str) stk 
     | (c == '(') = verify str (push c stk) 
     | (c == ')') = if isEmpty stk then False else if top stk == '(' then verify str (pop stk) else False 
     | (c == '[') = verify str (push c stk) 
     | (c == ']') = if isEmpty stk then False else if top stk == '[' then verify str (pop stk) else False 
+0

Has trabajado en tu solución @rizo – ampc

3
import Data.Maybe 
import Control.Monad 

parse :: String -> Maybe String 
parse [email protected](')':_) = return xs 
parse [email protected](']':_) = return xs 
parse ('(':xs) = do 
    ')':ys <- parse xs 
    parse ys 
parse ('[':xs) = do 
    ']':ys <- parse xs 
    parse ys 
parse (_:xs) = parse xs 
parse [] = return [] 

paren :: String -> Bool 
paren xs = isJust $ do 
    ys <- parse xs 
    guard (null ys) 
2
import Data.Char 

verifier :: String -> Bool 
verifier x = balancer x [] 
    where 
balancer [] stack = null stack 
balancer (x:xs) [] = balancer xs [x] 
balancer (x:xs) (y:ys) = if isSpace x then balancer xs (y:ys) 
       else if x `elem` "([{" then balancer xs (x:y:ys) 
        else if (x == ')' && y == '(') || 
        (x == ']' && y == '[') || 
        (x == '}' && y == '{') then balancer xs ys 
       else False 
+1

Give también explicación –

+0

@SujithPS Comenzamos con una pila vacía. Presione un soporte de apertura cuando aparezca, y si aparece un corchete cerrado verifique si la parte superior de la pila contiene el corchete de apertura correspondiente. Si lo hace, páselo y proceda, de lo contrario informe de error. Al final del análisis, si el stac k está vacío, es una secuencia válida. – ssh

Cuestiones relacionadas