我正在尝试使用Java实现一个简单的Lisp表达式计算器。事实上，关于这个主题有很多信息，但它们似乎都使用了两个单独的堆栈来得出结果。我想知道是否有可能只使用一个堆栈来实现这样的程序，以及一些伪代码可能是什么样子的。
谢谢。
有关我所说的更多信息，请参阅
- http://www.chegg.com/homework-help/questions-and-answers/outline-given-import-javautil-public-class-simplelispexpressionevaluator-current-input-lis-q2332957
- http://stdioe.blogspot.ca/2012/01/lets-implement-simple-lisp-interpreter.html
您链接到的两个解释器都做出了一个非常重要的假设：+、-、*等都是二进制函数，也就是说，它们总是只接受两个参数。在真正的Lisp中，你可以说(+ 1 2 3 4 5)来求一堆数字的和。但是，如果你愿意接受每个运算符的arity都是已知的简化假设，那么你肯定只需要一个堆栈就可以做到这一点。关键是：将堆栈倒置。
你链接到的口译员有这样的堆栈：
底部->( + ( - 2 1 ) 4 )<-顶部(我们从这里推送和弹出)
但是，你也可以从右边向后阅读你的表达式，并像这样构建堆栈：
top->( + ( - 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关于忽略括号。只要你输入的表达式是格式良好的，这将非常有效，但它可以采用格式不正确的表达式，并赋予它们荒谬的值。例如CCD_ 24被解释为CCD_。如果您想防止这种行为，只需将圆括号推到堆栈上即可。当需要调用运算符时，弹出参数，再加上一个额外的令牌请确保该令牌是一个闭合的paren，否则会引发错误。一旦你有了结果，就把它推到堆栈上确保您读入的下一个令牌是一个打开的paren，然后丢弃它。
PPS如果像在真实的Lisp中一样，函数的参数本身可以是函数，那么这一切就会变得复杂得多。然后，您就没有RPN所依赖的运算符/操作数之间的方便区分，需要更多地注意作为分组元素的括号。我不确定您是否可以使用一个完整的Lisp表达式计算器，将变量arity和函数作为操作数，只使用一个堆栈。
希望它能帮助您无堆栈的lisp型计算器