Я должен записать функцию 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
Таким образом, я должен реализовать a par
функция, которая протестировала бы строку круглых скобок и сказала бы, сбалансированы ли круглые скобки в ней или нет. Как я могу сделать то использование стека?
module Parens where
import Data.Map (Map)
import qualified Data.Map as Map
matchingParens :: Map Char Char
matchingParens = Map.fromList [
('(', ')')
, ('{', '}')
, ('[', ']')
]
isOpening :: Char -> Bool
isOpening c = maybe False (const True) $ Map.lookup c matchingParens
type Stack a = [a]
balanced :: String -> Bool
balanced = balanced' []
balanced' :: Stack Char -> String -> Bool
balanced' [] "" = True
balanced' _ "" = False
balanced' [] (c:cs) = balanced' [c] cs
balanced' (o:os) (c:cs)
| isOpening c = balanced' (c:o:os) cs
| otherwise = case Map.lookup o matchingParens of
Nothing -> False
Just closing -> if closing == c
then balanced' os cs
else False
Я новичок в 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
Вот ответ:
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