我编写了以下程序来检查字符串是否平衡括号:
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