检查一个字符串是否包含平衡括号 [英] 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 = [
    isBalanced "",
    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

推荐答案

由于 Henning说，解析器组合器会为此工作。以下是使用 Parsec 的示例：

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

这篇关于检查一个字符串是否包含平衡括号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！