Я написал следующую программу для проверки строк на наличие сбалансированных скобок:
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)
Вот несколько примеров данных:
positives = [
isBalanced "",
isBalanced "()",
isBalanced "[]",
isBalanced "{}",
isBalanced "([]){}[{}]"
]
negatives = [
isBalanced "(",
isBalanced "[",
isBalanced "{",
isBalanced ")",
isBalanced "]",
isBalanced "}",
isBalanced "([)]",
isBalanced "{]",
isBalanced ")("
]
Поскольку в этой программе используются только самые основные строительные блоки явной рекурсии, я подумал, есть ли более короткий и высокоуровневый подход с использованием языковых средств, о которых я еще не знаю.
Хорошо, я извлек следующее решение из нескольких ответов и комментарии (и мои собственные мысли):
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