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 the parentheses in it are balanced or not. How can I do that using a stack?
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With