Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Stack-based bracket matcher in Haskell
module Main
where
data Node = Node { chr :: Char
, next :: Maybe Node }
deriving (Show)
prepareInput :: String -> String
prepareInput str = filter (\c -> c `elem` ['(', ')']) str
processChar :: Char -> String -> Maybe Node -> Maybe Node
processChar '(' "" Nothing = Just (Node '(' Nothing) -- init case
processChar ')' r (Just n) = process r (next n)
processChar ')' _ Nothing = Just (Node ')' Nothing) -- error, generate a dummy
processChar '(' r stack = process r (Just (Node '(' stack))
-- Todo: Integrate this function into the `process` function as soon as it
-- works.
process :: String -> Maybe Node -> Maybe Node
process [] Nothing = Nothing
process [] stack = stack
process str stack = processChar (head str) (tail str) stack
-- We actually don't care when `stack` is Nothing and pass it to the
-- `processChar` function
answer :: Maybe Node -> String
answer Nothing = "OK"
answer _ = "Nup"
main :: IO ()
main = do
str <- getLine
putStrLn $ answer $ process (prepareInput str) Nothing
@Heimdell

This comment has been minimized.

Copy link

@Heimdell Heimdell commented Nov 19, 2014

Compare with: https://gist.github.com/Heimdell/3f483c02226d95faf1ee

Use specialized solutions for parsing - Parsec/Attoparsec/ReadP/Whatever.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment