Проверка, состоит ли строка из сбалансированных скобок

Я написал следующую программу для проверки строк на наличие сбалансированных скобок:

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
11
задан hammar 29 August 2011 в 01:38
поделиться