Randall

balance.hs

-- Coding For Interviews Problem #21
-- Problem: Balancing Delimeters
-- Author: Randall R. Van Why
-- Date: 2014-06-17

import Control.Monad

type Stack a = [a]

push :: a -> Stack a -> Stack a
push x y = (x:y)

peek :: Stack a -> Maybe a
peek (x:xs) = Just x
peek [] = Nothing

pop :: Stack a -> Stack a
pop (x:xs) = xs
pop [] = []

{-|
  Checks a character string for balanced delimeters
  using the maybe monad.
-}
isBalanced :: [Char] -> Bool
isBalanced s = Nothing /= foldM (flip check) [] s

{-|
  Checks a character against an existing stack.
  If left delimeter, pushes delimeter onto stack.
  If right delimeter, checks the top of the stack for
  a matching left delimeter. If one is not found,
  returns nothing.
-}
check :: Char -> Stack Char -> Maybe (Stack Char)
check '{' x = return $ push '{' x
check '(' x = return $ push '(' x
check '[' x = return $ push '[' x
check '}' x = if peek x == Just '{' then return $ pop x else Nothing
check ']' x = if peek x == Just '[' then return $ pop x else Nothing
check ')' x = if peek x == Just '(' then return $ pop x else Nothing