Java中的Lisp表达式求值程序（仅使用一个堆栈）
我正在尝试使用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已知的简化假设，那么你肯定只用一个堆栈就可以做到这一点。 关键：翻转堆栈。
你链接的解释器有这样的堆栈：
bottom – > ( + ( - 2 1 ) 4 ) < - top（我们从这里推送）
但是，您也可以从右侧向后读取表达式，并像这样构建堆栈：
top – > ( + ( - 2 1 ) 4 ) < - bottom
然后你基本上得到RPN，反向抛光表示法。 RPN非常适合堆栈。
算法是这样的：
- 如果看到括号，请忽略它
- 如果看到操作数，请将其推入堆栈
- 如果您看到一个运算符，请调用它。 操作符弹出所需数量的值，然后将其结果推送到堆栈
举例来说， ( + ( - 2 1 ) 4 ) 。 这是算法的运作方式：
Stack： empty 读取:) 动作：括号被忽略。 左： ( + ( - 2 1 ) 4
Stack： empty 读取： 4 动作：操作数被推送到堆栈。 左： ( + ( - 2 1 )
Stack： 4 阅读：） 动作：括号被忽略。 左： ( + ( - 2 1
Stack： 4 读取： 1 动作：操作数被推送到堆栈。 左： ( + ( - 2
Stack： 1 4 阅读： 2 动作：操作数被推送到堆栈。 左： ( + ( -
Stack： 2 1 4 阅读： - Action：调用operator。 它将从堆栈中弹出2和1，然后按2-1=1进入它。 左： ( + (
Stack： 1 4 阅读:( 动作：括号被忽略。 左： ( +
Stack： 1 4 阅读： + Action：调用operator。 它将从堆栈中弹出1和4，然后将1+4=5推入其中。 左:(
Stack： 5 阅读:( 动作：括号被忽略。 左： 没有
完成！ 结果是5，正如预期的那样。
PS关于忽略括号。 只要您输入的表达式格式正确，这将完美地工作，但它可以采用非格式良好的表达式并赋予它们无意义的值。 例如(+ - + 1 2 3 4)被解释为(+ (- (+ 1 2) 3) 4) 。 如果您想要阻止此行为，只需将紧密括号推入堆栈即可。 当需要调用操作符时，弹出参数，再加上一个额外的标记。 确保令牌是紧密的，否则抛出错误 。 获得结果后，将其推入堆栈。 确保您读入的下一个令牌是开放式的，然后将其丢弃 。
如果像在真正的Lisp中那样，函数的参数本身就是函数，那么PPS就会变得复杂得多。 那么你没有RPN所依赖的操作符/操作数之间的便利区别，你需要更多地关注括号作为分组元素。 我不确定你是否可以做一个完整的Lisp表达式求值程序，它具有变量arity和函数作为操作数，只有一个堆栈。
希望它可以帮助你没有堆栈的lisp风格计算器