News for hackers. Stuff that matters.
Re:A Brutal Look at Balanced Parentheses, Computing Machines... by antidesitter on Friday February 22, 2019 @06:11PM (#19230032)
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
Re:A Brutal Look at Balanced Parentheses, Computing Machines... by Tarean on Saturday February 23, 2019 @06:02AM (#19232730)
My 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 []