How to write Haskell function to verify parentheses matching?

Question

I need to write a function par :: String -> Bool to verify if a given string with parentheses is matching using stack module.

Ex:

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

Here's my stack module implementation:

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

So I need to implement a 'par' function that would test a string of parentheses and say if parentheses in it matches or not. How can I do that using a stack?

Answer 1

Here's the answer:

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 2

I am a haskell newbie. Here's my attempt, definitely inelegant but wanted to try a different approach

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 3

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