java - 使用 Java 堆栈评估有效的 Lisp 表达式

Question

对于 中的项目Data Structures，我们鼓励Lisp Expression使用来评估Java API Stacks。

有Lisp expressions四个基本运算符：+, -, *, / . 表达式中的有效标记是'(', ')', 和运算符。

一个例子Lisp expression： ( + (-6) (+ 3 2 1) (/ 10 5) (* 2 3 4))等于26。

---

如何计算 的令牌Lisp，然后将它们推回stack？

Answer 1

这是食谱（是的，你必须了解Java，没有其他办法）

• 标记您的输入：您将拥有以下标记
  • S-EXPR-START（每次遇到'(')
  • S-EXPR-END（每次遇到')'）
  • NUMBER（值是解析的数字的值）
  • OPERATION（值是操作码：+-*/等）
• 构建语法树：每次启动 s 表达式（左括号）时，它都是一个新的树节点，它的值是函数，子节点是操作数。
• 通过用该节点的结果替换节点/子节点，以自下而上的方法评估您的树。...
• 利润！