题解 P1928 【外星密码】
HoshinoTented
2020-01-08 21:51:48
这一道题是比较常见的 Parser 题，我曾经也写过一点 Parser，所以就用 Parser 的方式来解决这道题了。
## Parse
首先我们要解析整个密码，就需要一个函数 `parse'`：
```haskell
-- 解析 :: 密码 -> (明文, 剩余代码)
parse' :: String -> (String, String)
parse' ('[':xs) = undefined
```
但我们目前还没办法实现这个函数，先试试实现其他函数吧。
## readNumber
解析密码首先需要读取对应的数字：
```haskell
-- 解析数字 :: 数字字符串 -> 缓存区 -> (解析结果，剩余代码)
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
接下来就要解析字符串了：
```haskell
-- 解析字符串 :: 字符串 -> 缓存区 -> (解析结果，剩余代码)
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'` 函数了：
```haskell
-- 解析 :: 密码 -> (明文，剩余代码)
parse' :: String -> (String, String)
parse' ('[':xs) = let -- 如果是 '[' 开头，则进行解析
(count, remain) = readNumber xs "" -- 先读取数字
(str, remain') = readString remain "" in -- 再读取字符串
([1..count] >> str, remain') -- 最后将字符串都连接起来，返回剩余代码
```
在 GHCi 中测试一下，发现返回的字符串是倒序的：
```haskell
*P1928> readString "AC[3FUN]" ""
("NUFNUFNUFCA","")
```
所以再写一个辅助函数：
```haskell
parse :: String -> String
parse = reverse . fst . flip readString ""
```
## Main
最后补全 `main` 函数：
```haskell
main :: IO ()
main = do
str <- getLine
putStrLn $ parse str
```
AC 啦！
## State Monad
代码中有许多形如 `s-> (a, s)` 的函数签名，理论上可以用 State Monad 进行优化，但是我太懒了，就没优化。