11

文字列の括弧のバランスをチェックするために、次のプログラムを作成しました。

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
4

4 に答える 4

18

ヘニングが言ったように、パーサーコンビネーターはこれで機能します。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
于 2011-08-26T19:30:02.697 に答える
10

左折の使い方

import Data.List (foldl')

isBalanced xs = null $ foldl' op [] xs
  where
    op ('(':xs) ')' = xs
    op ('[':xs) ']' = xs
    op ('{':xs) '}' = xs
    op xs x = x:xs

折り畳みは、以前に遭遇した文字のスタックを構築し、一致するものを見つけたら取り除きます。空のリストになった場合、文字列はバランスが取れています。

Maybe モナドで左折畳みを使う

左折りを使用することの欠点は、文字列全体を常にスキャンする必要があることです。一致する左中括弧なしで右中括弧が見つかった場合は、失敗して操作を中止するとよいでしょう。これはまさにそれを行うバージョンです。

import Control.Monad (foldM)

isBalanced' xs = maybe False null $ foldM op [] xs
  where
    op ('(':xs) ')'          = Just xs
    op ('[':xs) ']'          = Just xs
    op ('{':xs) '}'          = Just xs
    op xs x | x `elem` ")]}" = Nothing
            | otherwise      = Just (x:xs)
于 2011-08-26T20:06:17.287 に答える
3

hammarの答えが最良だと思いますが、実行できる小さな手順を次に示します- and を使用nullしlookupます:

{-# LANGUAGE PatternGuards #-}
isBalanced xs = isBalanced' xs []

isBalanced' [] x = null x

isBalanced' (c:xs) ys | Just d <- lookup c par = isBalanced' xs (d:ys)
  where par = [('(',')'), ('[',']'),('{','}')]

isBalanced' _  [] = False

isBalanced' (x:xs) (y:ys) = x == y && isBalanced' xs ysl

あなたの例positivesとnegativesデータは間違いなくmap、または を使用する必要がありallます。

于 2011-08-26T19:41:30.777 に答える
2

この単純な問題にはやり過ぎかもしれませんが、パーサー コンビネーターを調べてみてください。

より基本的な単純化として、再帰を書き直して、スタックと文字列から新しいスタックへの文字を取得する関数を折りたたむことができます。（ただし、これが実際に簡単になるかどうかは、見る人の目にかかっています）。

于 2011-08-26T18:58:41.373 に答える