How to write Haskell function to verify parentheses matching?
Posted
by Rizo
on Stack Overflow
See other posts from Stack Overflow
or by Rizo
Published on 2010-05-28T08:42:55Z
Indexed on
2010/05/28
9:21 UTC
Read the original article
Hit count: 748
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?
© Stack Overflow or respective owner