4

这是我想出的：

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

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

4

5 回答 5

9

  1. 将堆栈的类型更改为Integral a => [a]. 这不仅消除了对无处不在的需求，read而且show还揭示了原始代码中隐藏的类型错误。您使用的是小数除法 ( /) 而不是整数除法 ( div)。

  2. 反转堆栈。列表更容易从前面操作，因此将其用作堆栈的顶部。这也让我们可以在堆栈上使用模式匹配来轻松地从堆栈顶部挑选元素，而不是乱用lastand 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)]

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

Either为了健壮性，使用纯粹的错误处理形式（如orMaybe代替 usingerror和 usereads而不是read处理格式错误的输入）可能也是一个好主意。

于 2012-04-17T09:29:52.600 回答
6

其他人已经告诉了您几乎所有内容以改进您的代码。我只是想补充一点，《Learn You a Haskell , Functioanlly Solve Problems 》一书中有一章写得非常好，它的第一部分准确地解释了如何使用foldl.

于 2012-04-17T10:12:08.613 回答
5

如果你定义

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

写一个合适的

parseToken :: String -> Token a

并重写solveRPN以使用此签名

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

然后变得有些琐碎isOperator，calcFunction您可以避免所有乏味的reading和showing。

但是，您必须停止捏造除法问题：/仅适用于Fractional(not Integral) 类型。到目前为止，您一直在逃避它，因为您每次都在从字符串转换为字符串，因此当您进行除法时，数字已转换为小数类型。您必须决定是否要使用div或quot替代，或者是否要使用小数类型。

（另外，parseTokenand的结果solveRPN应该被包裹在里面Maybe（或一个Either类型），这样你就可以指示失败Nothing而不是抛出异常。）

于 2012-04-17T09:28:52.273 回答
3

有效地使用列表（简单）

使它更惯用的一个简单方法是反转stack（这使它更像一个真正的堆栈），它允许您使用模式匹配并使代码更高效，因为在列表头部附加/读取是一个O(1)操作，最后这样做是O(n)：

solveRPN :: (Read a, Integral a) => [String] -> [String] -> a
solveRPN [] (x:[]) = read x
solveRPN [] (x:y:xs) = solveRPN (y:x:[]) xs -- push them on backwards
solveRPN stack@(s1:s2:rest) (x:xs) -- pattern match on stack with length >= 2
         | isOperator x =
           let z = calcFunction x s2 s1
           in solveRPN rest (z:xs)
         | otherwise = solveRPN (x:stack) xs
solveRPN stack (x:xs) -- last case: list with a single element
         | isOperator x = error "Stack too small"
         | otherwise = solveRPN (x:stack) xs

使用类型系统（重要！）

您正在使用字符串来封装输入堆栈上的两种可能类型：操作和数字，这允许无效输入，惯用的 Haskell 将利用类型系统，以便函数始终具有定义的结果（即所有函数都是总的） .

最好使用 ADT（代数数据类型）来封装可能的操作，并Either以类型安全的方式区分操作和文字：

data Operation = Plus | Minus | Times | Divide

-- conversion function
readStackVar :: (Read a) => String -> Either Operation a
readStackVar "+" = Left Plus
readStackVar "-" = Left Minux
readStackVar "*" = Left Times
readStackVar "/" = Left Divide
readStackVar other = Right . read $ other

这使您可以很好地编写isOperator（尽管现在实际上没有必要）：

isOperator :: Either Operation a -> Bool
isOperator (Left _) = False
isOperator _ = True

calcFunction现在是类型安全的（注意类型没有Either），并且不可能进行无法识别的操作：

calcFunction :: (Integral a) => Operation -> a -> a -> a
calcFunction Plus = (+)
calcFunction Minus = (-)
calcFunction Times = (*)
calcFunction Divide = div -- integral division

使用这些我们可以重写solveRPN（注意我们已经避免了solveRPN 通过使用 where 子句传递一个空列表）：

solveRPN :: (Read a, Integral a) => [Either Operation a] -> a
solveRPN xs = go [] xs
   where
     go :: (Read a, Integral a) => [a] -> [Either Operation a] -> a
     go [] [] = error "Empty"
     go (x:xs) [] = x -- finished all the input
     go [] (x:y:xs) = go (y:x:[]) xs -- start the stack in reverse order

     go (s1:s2:rest) ((Left op):xs) = go ((calcFunction op s1 s2) : rest) xs -- operation   
     go stack ((Right x):xs) = go (x:stack) xs -- literal

请注意，我已经能够在Leftand Rightof上使用模式匹配Either来区分操作和文字。（我们可以（并且应该）做的另一件事是 make solveRPNreturn Maybe a，这样可以通过返回来指示错误，通过返回来指示Nothing成功Just x。）

这像这样使用：

solveRPN . map readStackVar . words $ "1 2 + 3 *"

（警告：我还没有实际测试过这个，所以可能有拼写错误和小逻辑错误）

于 2012-04-17T09:38:29.480 回答
0

您可以使用Map键值对或仅使用键值对来存储操作：

ops = [("+",(+)),("-",(-)),("/",(/)),("*",(*))]

calcFunction :: String -> String -> String -> String
calcFunction op x y = go $ lookup op ops where
  go (Just f) = show $ read x `f` read y
  go Nothing = error $ "Unknown operator: " ++ op ++ "."

isOperator :: String -> Bool
isOperator op = elem op $ fst $ unzip ops
于 2012-04-17T14:07:03.243 回答