Verificando se uma string consiste em parênteses balanceados
Eu escrevi o seguinte programa para verificar as seqüências de caracteres entre parênteses balanceados:
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)
Aqui estão alguns dados de exemplo:
positives = [
isBalanced "",
isBalanced "()",
isBalanced "[]",
isBalanced "{}",
isBalanced "([]){}[{}]"
]
negatives = [
isBalanced "(",
isBalanced "[",
isBalanced "{",
isBalanced ")",
isBalanced "]",
isBalanced "}",
isBalanced "([)]",
isBalanced "{]",
isBalanced ")("
]
Como esse programa usa apenas os blocos mais básicos de recursão explícita, imaginei se havia uma abordagem mais curta e de alto nível envolvendo recursos de idiomas dos quais ainda não estou ciente.
Ok, destilei a seguinte solução a partir de várias respostas e comentários (e meus próprios pensamentos
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