balanced_parentheses.hs

module Main (main) where

import Control.Monad
import Control.Applicative

isOpener :: Char -> Bool
isOpener '('  = True
isOpener '['  = True
isOpener '{'  = True
isOpener _    = False

closes :: Char -> Char -> Bool
closes '(' ')'  = True
closes '[' ']'  = True
closes '{' '}'  = True
closes _ _      = False

isBalanced :: [Char] -> [Char] -> Bool
isBalanced [] []        = True
isBalanced _ []         = False -- No brackets left to close openers
isBalanced [] (y:ys)
  | isOpener y          = isBalanced [y] ys
  | otherwise           = False
isBalanced (x:xs) (y:ys) -- x:xs is stack of openers in reverse order from RHS
  | isOpener y          = isBalanced (y:x:xs) ys
  | x `closes` y = isBalanced xs ys
  | otherwise           = False

main :: IO ()
main = do
  t <- (read :: String -> Int) <$> getLine
  replicateM_ t $ do
    brackets <- getLine
    putStrLn $ if isBalanced [] brackets then "YES" else "NO"