Проверка, состоит ли строка из сбалансированных скобок - PullRequest
Новая
       70

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

11 голосов
/ 26 августа 2011

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

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 ]

17 голосов
/ 26 августа 2011

Как сказал Хеннинг , комбинаторы синтаксического анализа будут работать для этого.Вот пример использования 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
10 голосов
/ 27 августа 2011

Использование левой складки 

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)
2 голосов
/ 26 августа 2011

Я думаю, что ответ Хаммара - лучший, но вот меньшие шаги, которые вы можете сделать - используйте 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.

2 голосов
/ 26 августа 2011

Возможно, это слишком сложная задача, но вы можете попробовать поискать комбинаторы синтаксического анализа .

В качестве более простого упрощения вы можете переписать рекурсию в сворачивание функции, которая требуетстек и символ из строки в новый стек.(Будет ли это на самом деле проще, на взгляд смотрящего).

...