Haskell 使用 foldr 实现 rpn

Question

我正在尝试使用 foldr 编写一个反向波兰符号评估器，这是我目前所拥有的:

step :: [Int] -> String -> [Int] 
step (x * y):ys "*" = (x:y:ys)
step (x + y):ys "+" = (x:y:ys)
step (y - x):ys "-" = (x:y:ys)
step xs numberString = read numberString:xs

rpnRec ::[String] -> Int   
rpnRec [] = 1                                          
rpnRec = reverse .foldr step [] 

我试图通过交换 this 的位置来解决错误:(x * y):ys 和 this (x:y:ys)
但我不断收到此错误:

Rpn.hs:14:7: error: Parse error in pattern: x * y
   |
14 | step (x * y):ys "*" = (x:y:ys)
   |       ^^^^^
Failed, no modules loaded.

任何有关如何解决此问题的帮助将不胜感激。谢谢

Answer 1

这里有一些问题。第一个是您在 step 中交换“输入”和“输出”。功能。实际上，如果您遇到乘法( "*" )，您将从堆栈中弹出两个项目，并将乘法的结果压入堆栈。 step因此，函数应如下所示:

step :: [Int] -> String -> [Int] 
step (x:y:ys) "*" = x*y:ys
step (x:y:ys) "+" = x+y:ys
step (x:y:ys) "-" = x-y:ys
step xs numberString = read numberString:xs

(x:y:ys) 的括号这里是必要的，因为我们使用相同的参数:Int 的列表s。

此外你不能写foldr step []并期望它会产生 Int . foldr将返回累加器，即 Int 的列表s，因此 foldr step [] somelist :: [Int] .您可以使用例如 head获取第一个元素。

累加器和元素的类型应该交换，我们可以使用 flip :: (a -> b -> c) -> b -> a -> c 翻转两个参数。

最后，您应该反转字符串列表，而不是输出，因此该函数应如下所示:

rpnRec :: [String] -> Int
rpnRec = safeHead . foldr (flip step) [] . reverse
    where safeHead [] = 1
          safeHead (x:_) = x

例如:

Prelude> rpnRec ["2", "3", "*", "5", "+"]
11