Haskell 函数验证括号匹配

Question

我需要编写一个函数

par :: String -> Bool

来验证带括号的给定字符串是否使用堆栈模块匹配。

例如：

par "(((()[()])))" = True
par "((]())" = False

这是我的堆栈模块实现：

module Stack (Stack,
              push, pop, top,
              empty, isEmpty)
    where

data Stack a = Stk [a]
             deriving (Show)

push :: a -> Stack a -> Stack a
push x (Stk xs) = Stk (x:xs)

pop :: Stack a -> Stack a
pop (Stk (_:xs)) = Stk xs
pop _ = error "Stack.pop: empty stack"


top :: Stack a -> a
top (Stk (x:_)) = x
top _ = error "Stack.top: empty stack"

empty :: Stack a
empty = Stk []

isEmpty :: Stack a -> Bool
isEmpty (Stk [])= True
isEmpty (Stk _) = False

所以我需要实现一个

par

函数来测试一串括号并判断其中的括号是否平衡。我如何使用堆栈来做到这一点？

Answer 1

SO是一场狗屎秀。感谢您的搭车。

Answer 2

答案如下：

parent' :: String -> Stack Char -> Bool
parent' [] stk = isEmpty stk
parent' (c:str) stk
        | (c == '(') = parent' str (push c stk)
        | (c == ')') = if isEmpty stk then False
                       else if top stk == '(' then parent' str (pop stk)
                       else False



parent :: String -> Bool
parent [] = True
parent str = parent' str empty

Answer 3

import Data.Maybe
import Control.Monad

parse :: String -> Maybe String
parse xs@(')':_) = return xs
parse xs@(']':_) = return xs
parse ('(':xs) = do
  ')':ys <- parse xs
  parse ys
parse ('[':xs) = do
  ']':ys <- parse xs
  parse ys
parse (_:xs) = parse xs
parse [] = return []

paren :: String -> Bool
paren xs = isJust $ do
  ys <- parse xs
  guard (null ys)

Answer 4

我是一个 Haskell 新手。这是我的尝试，绝对不优雅，但想尝试不同的方法

data Stack a = Stk [a]
         deriving (Show)

push :: a -> Stack a -> Stack a
push x (Stk xs) = Stk (x:xs)

pop :: Stack a -> (Maybe a, Stack a)
pop (Stk []) = (Nothing, Stk [])
pop (Stk (x:xs)) = (Just x, Stk xs)

top :: Stack a -> Maybe a
top (Stk (x:_)) = Just x
top _ = Nothing

empty :: Stack a
empty = Stk []

isEmpty :: Stack a -> Bool
isEmpty (Stk [])= True
isEmpty (Stk _) = False 


par :: String -> Maybe (Stack Char)
par = foldl check (Just (Stk []))
      where check (Just stk) x
                | x == '(' = Just (push x stk)
                | x == ')' = case pop stk of
                                     (Just '(', newStk) -> Just newStk
                                     _ -> Nothing
            check Nothing x = Nothing


parCheck :: String -> Bool
parCheck xs = case par xs of
                Just stk -> isEmpty stk
                Nothing -> False

Answer 5

parent :: String -> Bool
parent "" = True
parent str = verify str empty

verify :: String -> Stack Char -> Bool
verify [] stk = isEmpty stk
verify (c:str) stk
        | (c == '(') = verify str (push c stk)
        | (c == ')') = if isEmpty stk then False else if top stk == '(' then verify str (pop stk) else False
        | (c == '[') = verify str (push c stk)
        | (c == ']') = if isEmpty stk then False else if top stk == '[' then verify str (pop stk) else False

Answer 6

import Data.Char

verifier :: String -> Bool
verifier x = balancer x []
    where
balancer [] stack = null stack
balancer (x:xs) [] = balancer xs [x]
balancer (x:xs) (y:ys)  = if isSpace x then balancer xs (y:ys)
              else if x `elem` "([{" then balancer xs (x:y:ys)
                  else if (x == ')' && y == '(') ||  
                  (x == ']' && y == '[') || 
                  (x == '}' && y == '{')  then balancer xs ys 
                else False

Answer 7

isOpenBracket :: Char -> Bool
isOpenBracket x = case x of 
    '{' -> True
    '[' -> True
    '(' -> True
    otherwise -> False  

isCloseBracket :: Char -> Bool
isCloseBracket x = case x of 
    '}' -> True
    ']' -> True
    ')' -> True
    otherwise -> False 

bracketLookup :: Char -> Char
bracketLookup x = case x of 
    '{' -> '}'
    '[' -> ']'
    '(' -> ')'

checkBrackets :: [Char] -> [Char] -> Bool 
checkBrackets [] []             = True
checkBrackets [] (x:xs)         = (isOpenBracket x) && (checkBrackets (x:[]) (xs))
checkBrackets (s:ss) (x:xs) 
    | (isOpenBracket x)         = (checkBrackets (x:s:ss) (xs))
    | (isCloseBracket x)        = (x == bracketLookup s) && checkBrackets (ss) (xs)
    -- case where x is not a a bracket (invalid char), just skip it
    | otherwise                 = checkBrackets (s:ss) (xs) 
checkBrackets (x:xs) [] = False

bracketParity x = checkBrackets "" x

我的尝试，只是使用列表作为堆栈并沿着输入重复。忽略非括号字符。

输出：

*Main> bracketParity "{()([a])}"
True
*Main> bracketParity "{()([aaaa])}"
True
*Main> bracketParity "{(a)([aaaa]a)}"
True
*Main> bracketParity "{()([])}"
True
*Main> bracketParity "[][][]"
True
*Main> bracketParity "[][][]]"
False