Funzione Haskell per verificare le parentesi corrispondenti a

Question

Devo scrivere una funzione par :: String -> Bool per verificare se una determinata stringa con parentesi corrisponde con il modulo stack.

Es:

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

Ecco la mia implementazione del modulo di stack:

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 

quindi ho bisogno di implementare una funzione par che testare una serie di parentesi e dire se le parentesi in esso sono bilanciati o no. Come posso farlo usando uno stack?

Answer 1

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 

Answer 2

Ecco la risposta:

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 

Answer 3

Sono un novizio Haskell. Ecco il mio tentativo, sicuramente poco elegante ma ha voluto provare un approccio diverso

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 

Answer 4

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 

Answer 5

import Data.Maybe 
import Control.Monad 

parse :: String -> Maybe String 
parse xs@(')':_) = return xs 
parse xs@(']':_) = 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) 

Answer 6

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