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: 395

Filed under:
|
|

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

Related posts about haskell

Related posts about stack