如何改进此Haskell函数以评估RPN表达式？

Question

这是我想出的:

solveRPNWrapper :: (Read a, Integral a) => String -> a
solveRPNWrapper str = solveRPN [] $ words str

calcFunction :: String -> String -> String -> String
calcFunction "+" x y = show $ read x + read y
calcFunction "-" x y = show $ read x - read y
calcFunction "*" x y = show $ read x * read y
calcFunction "/" x y = show $ read x / read y
calcFunction op x y = error $ "Unknown operator: " ++ op ++ "."

isOperator :: String -> Bool
isOperator "+" = True
isOperator "-" = True
isOperator "*" = True
isOperator "/" = True
isOperator _ = False

solveRPN :: (Read a, Integral a) => [String] -> [String] -> a
solveRPN [] (x:[]) = read x
solveRPN [] (x:y:xs) = solveRPN (x:y:[]) xs
solveRPN stack (x:xs)
         | isOperator x =
           let z = calcFunction x (last (init stack)) (last stack)
           in solveRPN (init (init stack)) (z:xs)
         | otherwise = solveRPN (stack ++ [x]) xs
solveRPN stack [] = error $ "Badly formatted expression: Stack contains " ++ show stack

虽然它确实有效......

*Main>  solveRPNWrapper "10 4 3 + 2 *  -"
-4

...我可以看到这不是惯用的(在操作符位中肯定有很多重复,读/显示似乎是多余的),并且约束也可能搞砸了.

Answer 1

1. 将堆栈类型更改为Integral a => [a].这不仅消除了需要read和show无处不在,但也揭示了你原来的代码隐藏类型的错误.您使用的是小数除法(/)而不是整数除法(div).

2. 反转堆栈.列表更容易从前面操作,因此将其用作堆栈的顶部.这也让我们可以使用堆栈上的模式匹配来轻松地从堆栈顶部拾取元素,而不是乱用last和init.这也更有效.

3. 为运算符使用查找表.这进一步减少了重复,我们可以只存储相应的Haskell函数(+,div直接等),在表中.

这是我在做出这些改变后最终得到的:

solveRPNWrapper :: (Read a, Integral a) => String -> a
solveRPNWrapper str = solveRPN [] $ words str

solveRPN :: (Read a, Integral a) => [a] -> [String] -> a
solveRPN [result] [] = result
solveRPN (y : x : stack) (token : tokens)
  | Just f <- lookup token operators = solveRPN (f x y : stack) tokens
solveRPN stack (token : tokens) = solveRPN (read token : stack) tokens
solveRPN stack [] = error $ "Badly formatted expression: Stack contains " ++ show (reverse stack)

operators :: Integral a => [(String, a -> a -> a)]
operators = [("+", (+)), ("-", (-)), ("*", (*)), ("/", div)]

您也可以使用折叠而不是递归,但这需要向包装器添加更多错误处理.我也考虑使用Integer而不是Integral a => a,但这只是改变类型签名的问题.

为了实现稳健性,使用纯粹形式的错误处理(如使用Either或Maybe代替使用)也可能是一个好主意error,并使用reads而不是read处理格式错误的输入.

Answer 2

其他人已经告诉你几乎所有的东西,以改善你的代码.我只是想补充一点,在" 了解你是一个Haskell,功能解决问题 "一书中有一个非常精美的章节,其第一部分详细解释了如何使用编写一个基本的反向Nolish符号计算器foldl.

Answer 3

如果你定义

data Token a = Literal a
             | Operator (a -> a -> a)

写一个合适的

parseToken :: String -> Token a

并重写solveRPN以使用此签名

solveRPN :: [a] -> [Token a] -> a

然后isOperator和calcFunction变得有些琐碎,而且你能避免所有的繁琐readING及showING.

但是,你必须停止捏造分裂问题:/仅适用于Fractional(非Integral)类型.到目前为止,你已经开始使用它了,因为你每次都要转换为字符串,所以当你进行除法时,数字已经被转换为小数类型.您必须决定是否要使用div或quot替代,或者是否要使用小数类型.

(此外,结果parseToken和solveRPN应该包含在内部Maybe(或Either类型),以便您可以指示失败,Nothing而不是抛出异常.)