检查平衡分隔符函数Haskell

voase2hg 于 2023-01-13 发布在其他

关注(0)|答案(2)|浏览(140)

我想写一个函数，你输入一系列的分隔符，元组，和一个字符串，然后这个函数会根据我们输入的元组来检查字符串是否平衡，然后返回一个布尔值。
例如：
输入：balanceList [('[','}')] "[}"
输出：True
输入：balanceList [('{',')'] "{}"
输出：False
下面是我目前的代码：

balanceList :: [(Char, Char)] -> String -> Bool
balanceList pairs string = balanced string emptyStack
  where
    balanced [] stack = isEmpty stack

    balanced (c:string) stack
      |c `elem1` (map fst pairs) = balanced string (push c stack)
      |c `elem1` (map snd pairs) = popTest (pop stack)
        where
          popTest Nothing = False
          popTest (Just (x,s)) = x == c && balanced string s

    balanced (_:string) stack  = balanced string stack

当我输入balanceList [('[','}')] "[}"时，得到的是False而不是True
我该如何解决这个问题？
先谢谢你

haskell

来源：https://stackoverflow.com/questions/75071892/check-balance-delimiters-function-haskell

2条答案

按热度按时间

ql3eal8s1#

使用push c stack，你是在栈上压入左括号，而不是右括号，因此当你检查它是否是右括号时，你会检查当前字符是否与左括号相同。
一个更简单的方法是将预期的右括号压入堆栈，这样就弹出了堆栈，类似于：

balanceList :: Eq a => [(a, a)] -> [a] -> Bool
balanceList pairs = go []
    where go [] [] = True
          go (c:ss) (c':cs)
            | c == c' = go ss cs -- closing parenthesis
          go s (c:cs)
            | Just c' <- lookup c pairs = …
          go _ _ = False

因此，我们首先检查堆栈和字符串是否都为空，然后返回True，如果堆栈和字符串都不为空，我们首先检查堆栈头c和字符串的第一个字符是否匹配，如果匹配，我们弹出堆栈并在字符串的尾部递归，如果失败，我们检查第一个字符c是否是pairs的一个元素，然后得到需要压入堆栈的共括号c'。

赞(0）回复(0）举报 2023-01-13

mwyxok5s2#

问题出在这一行：

|c `elem1` (map fst pairs) = balanced string (push c stack)

你在这堆东西里放了什么？

赞(0）回复(0）举报 2023-01-13

我来回答

检查平衡分隔符函数Haskell

2条答案

相关问题

热门标签

最新问答