12 ms·
Two purely-functional versions (written in Haskell): balanced1 input = let partialsums = scanl (+) 0 $ map (\x -> if x == '(' then 1 else -1) input
by antidesitter 8y ago
Two purely-functional versions (written in Haskell):
balanced1 input =
let partialsums = scanl (+) 0 $ map (\x -> if x == '(' then 1 else -1) input
in all (>= 0) partialsums && last partialsums == 0
balanced2 = balanced' 0 where
balanced' count [] = count == 0
balanced' count ('(':rest) = balanced' (count + 1) rest
balanced' count (')':rest) = balanced' (count - 1) rest && count > 0
A more general version with multiple types of brackets:
balanced = balanced' [] where
balanced' stack [] = null stack
balanced' stack ('(':rest) = balanced' ('(':stack) rest
balanced' stack ('[':rest) = balanced' ('[':stack) rest
balanced' stack ('{':rest) = balanced' ('{':stack) rest
balanced' stack (')':rest) = head stack == '(' && balanced' (tail stack) rest
balanced' stack (']':rest) = head stack == '[' && balanced' (tail stack) rest
balanced' stack ('}':rest) = head stack == '{' && balanced' (tail stack) rest
balanced' stack (_:rest) = balanced' stack rest
- Tarean 8y agoMy naive version would be import Control.Monad (foldM) checkBalanced :: [Char] -> Bool checkBalanced = isStackEmpty . foldM step mempty where step (x:xs) c | x == c = Just xs step ls c | Just r <- inverse c = Just (r : ls) step _ _ = Nothing inverse = flip lookup [( '(', ')' )] isStackEmpty stack = stack == Just []