时间戳

首页 > 解决方案 > 学习 Haskell 并想做一个反向波兰符号评估器

haskell - 学习 Haskell 并想做一个反向波兰符号评估器

问题描述

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

我想在诸如步骤[4,3,5]“+”中打印，并且在“”内它还可以使用读取函数提取整数。例如“3,4”但是我会得到

*Main> step [3,4,5,6,7,8,9] "+,3"
*** Exception: Prelude.read: no parse

希望我以后可以将它应用到以下带有 foldl 函数的 rpn 函数中！ 

rpn:: [String]->Int

谁能告诉我为什么或修复错误，拜托！

标签： haskell

解决方案

你需要仔细考虑step应该做什么。我怀疑您（最终）想要的是采用 RPN 字符串，例如：

"1 2 + 6 *"

将其分解为单个单词标记：

["1", "2", "+", "6", "*"]

然后将这些令牌一个一个地应用step到堆栈中。

因此，step应该接受一个初始堆栈和一个SINGLE令牌，并返回结果堆栈。例如，在"1"和"2"被处理之后，堆栈看起来像[2,1]，你想用这样的step方式应用"+"令牌：

> step [2,1] "+"
[3]

运算符的定义看起来不错：

step (x:y:ys) "*" = (x*y):ys
step (x:y:ys) "+" = (x + y):ys
step (x:y:ys) "-" = (x - y):ys

除了你可能想考虑减法运算符的x顺序y。大多数人会期望给出结果 5 ，"10 5 -"但是因为推入堆栈会给出一个] 堆栈，所以您的实现将计算而不是. 无论如何，您可以稍后再担心。105[5,10"-"5 - 1010 - 5

问题是另外两个定义：

step [] "" = []
step xs numString = read numString::[Int]

第一个似乎毫无意义。它说，在原始堆栈为空的特殊情况下，处理空令牌将使其为空。你什么时候处理一个空的令牌？如果您处理一个空令牌并且堆栈不为空，应该会发生什么？我认为您正在尝试将堆栈的初始状态构建到step函数中，但这将是foldl函数的责任，所以step不应该处理这个问题。摆脱它。

numString定义是错误的。它说，如果前面的算术运算符不匹配，我们将丢弃旧堆栈并将当前标记作为新堆栈读取。为此，令牌必须看起来像"[1,2,3,4]"，并且它将替换原始堆栈。你什么时候会有一个看起来像这样的令牌？为什么要丢弃原始堆栈？

相反，您希望能够处理由单个数字组成的令牌，例如"1". 处理这个问题的方法是将read其作为一个整数并将其推送到现有堆栈中：

step xs numString = read numString : xs

在这里，因为read numString在需要 a 的上下文中使用Int（因为它被添加到Ints 列表的头部），所以它将读取单个数字标记，例如"3"or "42"。如您所见，它将它推送到现有堆栈上，这正是您想要它做的事情：

> step [1,2,3] "42"
[42,1,2,3]

无论如何，使用更正的定义：

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 numString = read numString : xs

您现在可以看到处理上面的示例是如何工作的。在这里，我从一个空堆栈开始，然后在使用该step函数应用每个令牌时手动向前复制堆栈：

> -- processing "1 2 + 6 *"...
> step [] "1"
[1]
> step [1] "2"
[2,1]
> step [2,1] "+"
[3]
> step [3] "6"
[6,3]
> step [6,3] "*"
[18]

推荐阅读