1

我正在尝试使用 Java 实现一个简单的 Lisp 表达式求值器。实际上有大量关于该主题的信息，但似乎他们都使用两个单独的堆栈来得出结果。我想知道是否可以仅使用一个堆栈来实现这样的程序，以及一些伪代码可能看起来像什么。

谢谢。

有关我正在谈论的内容的更多信息，请参阅

4

2 回答 2

3

您链接到的两个解释器都做了一个非常重要的假设：+、-、* 等都是二元函数，也就是说，它们总是采用两个参数。在真正的 Lisp 中，你可以说(+ 1 2 3 4 5)对一堆数字求和。但是，如果您愿意接受每个运算符的数量已知的简化假设，那么您绝对可以只用一个堆栈来做到这一点。关键：将堆栈倒置。

您链接到的解释器具有如下堆栈：

底部 -> ( + ( - 2 1 ) 4 )<- 顶部（我们从这里推送和弹出）

但是，您也可以从右侧向后读取表达式，并像这样构建堆栈：

顶部 -> ( + ( - 2 1 ) 4 )<- 底部

然后你基本上得到RPN，反向波兰符号。RPN 在筹码方面表现得非常好。

算法是这样的：

  • 如果您看到括号，请忽略它
  • 如果你看到一个操作数，把它压入堆栈
  • 如果您看到一个运算符，请调用它。运算符根据需要弹出任意数量的值，然后将其结果压入堆栈

举个例子，( + ( - 2 1 ) 4 )。以下是该算法的运行方式：

堆栈： 空 阅读： ) 行动：括号被忽略。剩下： ( + ( - 2 1 ) 4

堆栈： 空 阅读： 4 操作：操作数被压入堆栈。剩下： ( + ( - 2 1 )

堆栈： 4阅读： ) 行动：括号被忽略。剩下： ( + ( - 2 1

堆栈： 4阅读： 1 动作：操作数被压入堆栈。剩下： ( + ( - 2

堆栈： 1 4读取： 2 操作：操作数被压入堆栈。剩下： ( + ( -

堆栈： 2 1 4读取： -操作：调用运算符。它将从堆栈中弹出 2 和 1，然后压入2-1=1它。 剩下： ( + (

堆栈： 1 4读数： ( 操作：忽略括号。剩下： ( +

堆栈： 1 4读取： + 操作：调用运算符。它将从堆栈中弹出 1 和 4，然后压入1+4=5它。 剩下： (

堆栈： 5阅读： ( 行动：括号被忽略。左： 无

完毕！结果是 5，正如预期的那样。

PS关于忽略括号。只要您输入的表达式格式正确，这将完美地工作，但它可以采用格式不正确的表达式并赋予它们无意义的值。eg(+ - + 1 2 3 4)被解释为(+ (- (+ 1 2) 3) 4). 如果您想防止这种行为，只需将右括号压入堆栈即可。当需要调用运算符时，弹出参数，加上一个额外的标记。确保该令牌是近括号，否则抛出错误。得到结果后，将其压入堆栈。确保您读入的下一个令牌是一个开放括号，然后将其丢弃。

如果像在真正的 Lisps 中一样，函数的参数本身可以是函数，那么 PPS 这一切都会变得更加复杂。那么您就没有 RPN 所依赖的运算符/操作数之间的方便区分，您需要更加注意括号作为分组元素。我不确定你是否可以做一个成熟的 Lisp 表达式求值器，具有可变参数和函数作为操作数，只有一个堆栈。

于 2012-10-31T08:11:36.433 回答
0

希望它可以帮助你 没有堆栈的 lisp 风格计算器

于 2013-01-13T16:08:37.603 回答