import Data.List

-- Stacks implemented in Haskell.
-- N.B.: in reality, you would just use a list directly!
type Stack a = [a]

push :: a -> Stack a -> Stack a
push x xs = x:xs

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

top :: Stack a -> a
top (x:xs) = x

empty :: Stack a -> Bool
empty [] = True
empty _ = False

-- Characters we want as opening or closing brackets.
opening, closing :: [Char]
opening = "([{"
closing = ")]}"

-- Give the corresponding closing bracket for an opening bracket.
-- E.g., matching '(' == ')'.
matching :: Char -> Char
matching c = closing !! i
  where
    Just i = elemIndex c opening

-- Bracket matching. Start with an empty stack.
brackets :: String -> Bool
brackets xs = brackets' [] xs

-- Bracket matching with an extra parameter for the stack.
brackets' stack [] = empty stack
brackets' stack (x:xs)
    -- Open bracket.
  | x `elem` opening = brackets' (push x stack) xs
    -- Closing bracket, empty stack.
  | x `elem` closing && empty stack = False
    -- Closing bracket, non-matching value on stack.
  | x `elem` closing && matching (top stack) /= x = False
    -- Correct closing bracket.
  | x `elem` closing = brackets' (pop stack) xs
    -- Normal character.
  | otherwise = brackets' stack xs