Haskell嵌套结构反转代码异常：无法输出预期结果

原代码直接对字符串中的字符进行反转，没有正确识别括号组内的元素边界（空格分隔的原子或嵌套括号组），导致嵌套结构被错误拆解，最终输出不符合预期。比如原输入中的(L M (X Y))被当成字符序列反转，而不是把其中的三个元素L、M、(X Y)反转后重新组合。

正确的做法是先将字符串解析为结构化的表达式，再递归反转每个列表的元素顺序，最后重新序列化为字符串。这样能精准处理嵌套的括号结构，保证元素级别的反转。

修复后的完整代码 #

import Data.List (intercalate)

-- 定义表达式数据类型：原子（如P、L）或列表（括号包裹的元素集合）
data Expr = Atom String | List [Expr] deriving (Show)

-- 解析字符串为Expr
parseExpr :: String -> Expr
parseExpr s = case parseHelper (trim s) of
    (expr, "") -> expr
    _          -> error "Invalid input"
  where
    trim = reverse . dropWhile isSpace . reverse . dropWhile isSpace
    isSpace c = c `elem` " \t\n"

    parseHelper :: String -> (Expr, String)
    parseHelper ('(':rest) = 
        let (elems, ')':rest') = parseElements rest []
        in (List elems, rest')
    parseHelper s = 
        let (atom, rest) = span (\c -> not (isSpace c) && c /= '(' && c /= ')') s
        in (Atom atom, dropWhile isSpace rest)

    parseElements :: String -> [Expr] -> ([Expr], String)
    parseElements s acc
        | null s = (reverse acc, "")
        | head s == ')' = (reverse acc, s)
        | otherwise = 
            let (expr, rest) = parseHelper s
            in parseElements rest (expr:acc)

-- 递归反转每个列表的元素顺序
reverseExpr :: Expr -> Expr
reverseExpr (Atom s) = Atom s
reverseExpr (List xs) = List (reverse (map reverseExpr xs))

-- 将Expr序列化为字符串
showExpr :: Expr -> String
showExpr (Atom s) = s
showExpr (List xs) = "(" ++ intercalate " " (map showExpr xs) ++ ")"

-- 对外暴露的反转函数
reverseGroups :: String -> String
reverseGroups = showExpr . reverseExpr . parseExpr

main :: IO ()
main = do
    putStrLn "Enter something"
    inputString <- getLine
    let output = reverseGroups inputString
    putStrLn $ "Input: " ++ show inputString
    putStrLn $ "Output: " ++ show output

代码说明 #

1. 数据类型定义：Expr区分原子（单个标识符，如P、X）和列表（括号包裹的元素集合），为结构化处理提供基础。
2. 解析函数：parseExpr将输入字符串转换为Expr结构，通过parseHelper递归处理嵌套括号，parseElements分割列表内的元素（自动跳过空格）。
3. 反转逻辑：reverseExpr递归处理每个表达式，对列表类型反转其元素列表，原子类型保持不变。
4. 序列化函数：showExpr将反转后的Expr转回符合格式的字符串，列表用括号包裹，元素间用空格分隔。

测试验证 #

输入(P (L M (X Y)) f)，输出为(f ((Y X) M L) P)，完全符合预期。

内容的提问来源于stack exchange，提问作者Oblivion_HHY