时间戳

首页 > 解决方案 > 使用 foldl 的 Haskell 函数组合

haskell - 使用 foldl 的 Haskell 函数组合

问题描述

我在haskell中定义了以下函数：

step :: [Int] -> [Char] -> [Int]
step stack str
    | str == "*" =  remaining ++ [x*y] 
    | str == "+" =  remaining ++ [x+y]
    | str == "-" =  remaining ++ [x-y]
    | str == "/" =  remaining ++ [x `div` y]
    | otherwise = stack ++ [read str :: Int] 
    where x = (last . init) stack
          y = (last stack)
          remaining = (init . init) stack

此函数采用整数数组[10, 4, 3]和字符串运算符*，并将运算符应用于数组中的最后两项并返回以下数组[10, 7]。

这是一个中间函数的一部分，最终结果是一个反向波兰符号评估函数。

如何利用step我定义的功能并foldl执行以下操作：

以示例字符串："10 4 3 + 2 * -".

将每个元素添加到字符串中，直到遇到第一个运算符，如下所示：

10, 4, 3然后将运算符应用于堆栈顶部的两个元素并将结果放入堆栈：

10, 7.

如此继续，直到评估最终答案 ( -4)

回答：

为了完整起见，这是我在@talex 的帮助下得到的功能

rpn :: String -> Int
rpn input = head result
    where arr = words input
          result = foldl step [] arr

标签： haskellfoldfoldleft

解决方案

foldl step [] ["10",  "4", "3", "+", "2", "*", "-"]

[]这是初始堆栈。

如果您以以下方式重写您的步骤，它将更快地工作：

step :: [Int] -> [Char] -> [Int]
step stack str
        | str == "*" =  (x*y):remaining 
        | str == "+" =  (x+y):remaining
        | str == "-" =  (x-y):remaining
        | str == "/" =  (x `div` y):remaining
        | otherwise = (read str :: Int):stack
        where x = head $ tail stack
              y = head stack
              remaining = tail $ tail stack

推荐阅读