Checking if a string consists of balanced parenthesis
I wrote the following program to check strings for balanced parenthesis:
isBalanced xs = isBalanced' xs []
isBalanced' [] [] = True
isBalanced' [] _ = False
isBalanced' ('(':xs) ys = isBalanced' xs (')':ys)
isBalanced' ('[':xs) ys = isBalanced' xs (']':ys)
isBalanced' ('{':xs) ys = isBalanced' xs ('}':ys)
isBalanced' _ [] = False
isBalanced' (x:xs) (y:ys) = (x == y) && (isBalanced' xs ys)
Here is some example data:
positives = [
i开发者_如何学GosBalanced "",
isBalanced "()",
isBalanced "[]",
isBalanced "{}",
isBalanced "([]){}[{}]"
]
negatives = [
isBalanced "(",
isBalanced "[",
isBalanced "{",
isBalanced ")",
isBalanced "]",
isBalanced "}",
isBalanced "([)]",
isBalanced "{]",
isBalanced ")("
]
Since this program uses only the most basic building blocks of explicit recursion, I wondered if there was a shorter, more high-level approach involving language facilities I am not yet aware of.
Okay, I distilled the following solution from several answers and comments (and my own thoughts):
import Text.Parsec
grammar = many parens >> return () where
parens = choice [ between (char opening) (char closing) grammar
| [opening, closing] <- ["()", "[]", "{}"]]
isBalanced = isRight . parse (grammar >> eof) ""
isRight (Right _) = True
isRight _ = False
As Henning said, parser combinators would work for this. Here's an example using Parsec:
import Text.Parsec
grammar = many braces >> return ()
where braces = choice [ between (char '(') (char ')') grammar
, between (char '[') (char ']') grammar
, between (char '{') (char '}') grammar
]
isBalanced :: String -> Bool
isBalanced input = case parse (grammar >> eof) "" input of
Left _ -> False
Right _ -> True
Using a left fold
import Data.List (foldl')
isBalanced xs = null $ foldl' op [] xs
where
op ('(':xs) ')' = xs
op ('[':xs) ']' = xs
op ('{':xs) '}' = xs
op xs x = x:xs
The fold builds up a stack of previously encountered characters, stripping away any matches as it finds them. If you end up with an empty list, the string is balanced.
Using a left fold in the Maybe monad
The disadvantage of using a left fold is that the entire string must always be scanned through. It would be nice to abort the operation with a failure should a closing brace be found without a matching opening brace. Here's a version that does just that.
import Control.Monad (foldM)
isBalanced' xs = maybe False null $ foldM op [] xs
where
op ('(':xs) ')' = Just xs
op ('[':xs) ']' = Just xs
op ('{':xs) '}' = Just xs
op xs x | x `elem` ")]}" = Nothing
| otherwise = Just (x:xs)
I think hammar's answer is the best, but here are smaller steps you can do - use null
and lookup
:
{-# LANGUAGE PatternGuards #-}
isBalanced xs = isBalanced' xs []
isBalanced' [] x = null x
isBalanced' (c:xs) ys | Just d <- lookup c par = isBalanced' xs (d:ys)
where par = [('(',')'), ('[',']'),('{','}')]
isBalanced' _ [] = False
isBalanced' (x:xs) (y:ys) = x == y && isBalanced' xs ysl
Your example positives
and negatives
data should definitely use map
, or even all
.
Probably overkill for a problem this simple, but you could try looking up parser combinators.
As a more elementary simplification, you could rewrite your recursion into folding over a function that takes a stack and a character from the string to a new stack. (Whether this would make actually it simpler is in the eye of the beholder, though).
精彩评论