Last active
August 29, 2015 14:02
-
-
Save kyle-ilantzis/98f3b8e7dbcf8864757c to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| {- | |
| http://programmingpraxis.com/2014/06/10/balanced-delimiters-2/ | |
| Examples of strings that pass: {}, [], (), a(b)c, abc[d], a(b)c{d[e]} | |
| Examples of strings that don’t pass: {], (], a(b]c, abc[d}, a(b)c{d[e}] | |
| -} | |
| import Control.Monad(foldM,mapM_) | |
| isHead _ [] = False | |
| isHead x xs = x == head xs | |
| balanced = maybe False null . foldM read [] | |
| where | |
| read xs s | |
| | s `elem` ['{','(','['] = Just $ s:xs | |
| | s `elem` ['}',')',']'] = if (inv s) `isHead` xs then Just $ tail xs else Nothing | |
| | otherwise = Just xs | |
| inv '}' = '{' | |
| inv ')' = '(' | |
| inv ']' = '[' | |
| pass = [ "{}", "[]", "()", "a(b)c", "abc[d]", "a(b)c{d[e]}" ] | |
| fails = [ "{]", "(]", "a(b]c", "abc[d}", "a(b)c{d[e}]" ] | |
| expectPass = zip pass (repeat True) | |
| expectFails = zip fails (repeat False) | |
| main = mapM_ test $ expectPass ++ expectFails | |
| where | |
| test (str,expect) = let r = balanced str | |
| in putStrLn $ "balanced " ++ str ++ " = " ++ (show r) ++ ", expected " ++ (show expect) | |
| {- outputs: | |
| balanced {} = True, expected True | |
| balanced [] = True, expected True | |
| balanced () = True, expected True | |
| balanced a(b)c = True, expected True | |
| balanced abc[d] = True, expected True | |
| balanced a(b)c{d[e]} = True, expected True | |
| balanced {] = False, expected False | |
| balanced (] = False, expected False | |
| balanced a(b]c = False, expected False | |
| balanced abc[d} = False, expected False | |
| balanced a(b)c{d[e}] = False, expected False | |
| -} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment