Haskell自定义分隔符对的字符串平衡检查函数问题求助

我来帮你排查这个问题！你的代码逻辑方向是对的，但核心的匹配逻辑搞错了——这也是导致测试用例balanceList [('[','}')] "[}"返回False的原因。

问题根源 #

你当前的代码里，当遇到右分隔符时，是这么判断的：

popTest (Just (x,s)) = x == c && balanced string s

这里的x == c是直接比较弹出的左分隔符和当前右分隔符是否相等，但你的自定义分隔符对是不同字符（比如[和}），这一步永远不会成立，自然返回False。我们需要做的不是比较字符本身，而是检查弹出的左分隔符对应的右分隔符是否等于当前字符。

解决方案 #

我们需要先建立左分隔符到对应右分隔符的映射，这样当弹出左分隔符时，能快速查到它应该匹配的右分隔符。这里可以用两种方式实现：一种是用列表查找，另一种是用Data.Map优化查找效率（如果分隔符对很多的话）。

修改后的代码（用列表查找实现，无需额外导入）

balanceList :: [(Char, Char)] -> String -> Bool
balanceList pairs string = balanced string []  -- 直接用空列表模拟栈，简化实现

-- 辅助函数：根据左分隔符找到对应的右分隔符
getMatchingRight :: Char -> [(Char, Char)] -> Maybe Char
getMatchingRight _ [] = Nothing
getMatchingRight c ((l, r):rest)
  | l == c = Just r
  | otherwise = getMatchingRight c rest

balanced [] stack = null stack  -- 用null判断栈是否为空
balanced (c:string) stack
  -- 如果是左分隔符，压入栈
  | c `elem` (map fst pairs) = balanced string (c:stack)
  -- 如果是右分隔符，检查匹配逻辑
  | c `elem` (map snd pairs) = case stack of
      [] -> False  -- 栈为空，没有对应的左分隔符匹配
      (x:newStack) -> case getMatchingRight x pairs of
        Just expectedRight -> expectedRight == c && balanced string newStack
        Nothing -> False  -- 该左分隔符无对应右分隔符（理论上不会触发）
  -- 非分隔符字符直接跳过
  | otherwise = balanced string stack

用Data.Map优化的版本（适合大量分隔符对场景）

先导入Data.Map模块：

import qualified Data.Map as Map

再修改核心代码：

balanceList :: [(Char, Char)] -> String -> Bool
balanceList pairs string = balanced string []
  where
    -- 提前构建左分隔符到右分隔符的映射表
    leftToRightMap = Map.fromList pairs

balanced [] stack = null stack
balanced (c:string) stack
  | Map.member c leftToRightMap = balanced string (c:stack)
  | c `elem` (map snd pairs) = case stack of
      [] -> False
      (x:newStack) -> case Map.lookup x leftToRightMap of
        Just expectedRight -> expectedRight == c && balanced string newStack
        Nothing -> False
  | otherwise = balanced string stack

测试验证 #

现在测试你的第一个用例：

balanceList [('[','}')] "[}"

执行流程：

1. 遇到[，压入栈，栈变为['[']
2. 遇到}，弹出栈顶的[，查找到对应的右分隔符是}，和当前字符匹配，继续处理空字符串
3. 空字符串检查栈为空，返回True，符合预期

第二个用例：

balanceList [('{',')')] "{}"

执行流程：

1. 遇到{，压入栈，栈变为['{']
2. 遇到}，弹出{，对应的右分隔符是)，和当前的}不匹配，返回False，符合预期

额外小调整 #

你代码里的elem1应该是笔误，Haskell标准库中的判断元素是否存在的函数是elem；另外用普通列表模拟栈就足够简洁，不需要额外封装emptyStack、push、pop函数（当然如果有自定义栈类型需求也可以保留）。

备注：内容来源于stack exchange，提问作者RLP