题解 P1928 【外星密码】

· · 题解

这一道题是比较常见的 Parser 题，我曾经也写过一点 Parser，所以就用 Parser 的方式来解决这道题了。

Parse

首先我们要解析整个密码，就需要一个函数 parse'：

-- 解析 :: 密码 -> (明文, 剩余代码)
parse' :: String -> (String, String)
parse' ('[':xs) = undefined

但我们目前还没办法实现这个函数，先试试实现其他函数吧。

readNumber

解析密码首先需要读取对应的数字：

-- 解析数字 :: 数字字符串 -> 缓存区 -> (解析结果，剩余代码)
readNumber :: String -> String -> (Int, String)
readNumber [] tmp = (read $ reverse tmp, "")
readNumber (x:xs) tmp
    | isDigit x = readNumber xs (x:tmp)
    | otherwise = (read $ reverse tmp, x:xs)

由于用的是 (x:tmp) 而不是 (tmp ++ [x])（为了节约时间），所以需要在结束的时候用 reverse 函数将字符串翻转再进行 read。

readString

接下来就要解析字符串了：

-- 解析字符串 :: 字符串 -> 缓存区 -> (解析结果，剩余代码)
readString :: String -> String -> (String, String)
readString [] tmp = (tmp, "")       -- 如果字符串为空，返回缓存区的内容
readString ('[':xs) tmp = let (sub, remain) = parse' ('[':xs) in readString remain (sub ++ tmp)     -- 如果是 '[' 开头，说明是新的压缩区，使用 parse' 函数进行解析
readString (']':xs) tmp = (tmp, xs)   -- 如果是 ']'，说明已经到达结尾，返回缓存区内容和剩余代码
readString (x:xs) tmp = readString xs (x:tmp)       -- 如果都不是，则继续循环（递归）

Parse!

有了 readNumber 和 readString，就可以实现 parse' 函数了：

-- 解析 :: 密码 -> (明文，剩余代码)
parse' :: String -> (String, String)
parse' ('[':xs) = let           -- 如果是 '[' 开头，则进行解析
    (count, remain) = readNumber xs ""      -- 先读取数字
    (str, remain') = readString remain "" in        -- 再读取字符串
        ([1..count] >> str, remain')        -- 最后将字符串都连接起来，返回剩余代码

在 GHCi 中测试一下，发现返回的字符串是倒序的：

*P1928> readString "AC[3FUN]" ""
("NUFNUFNUFCA","")

所以再写一个辅助函数：

parse :: String -> String
parse = reverse . fst . flip readString ""

Main

最后补全 main 函数：

main :: IO ()
main = do
    str <- getLine

    putStrLn $ parse str

AC 啦！

State Monad

代码中有许多形如 s-> (a, s) 的函数签名，理论上可以用 State Monad 进行优化，但是我太懒了，就没优化。