构建一个数学表达式解析器/求值器？

Question

我正在尝试在Java中构建自己的数学表达式解析器，我知道有很多脚本管理引擎。但是我想自己构建一个，只是为了练习。

然而，我一直在寻找进展中的困难，所以我开始思考是否有更好的编写方式。这就是我的做法：

（同时我假设输入合法） 唯一合法的运算符是：+ - * / ^ ( )

我从用户获取一个字符串表达式输入，然后开始循环遍历字符串输入来查找“（”，如果我找到了一个，我会计算其内部的值，然后用结果替换子表达式字符串。

我应该继续按照这种方式编程，还是应该采取另一种方法？有没有任何教程可以解释如何完成这个任务（不是代码，仅仅是一般理论）？

感谢您的帮助。

- unknown unkonwn

---

个人认为自己编写解析器是很愚蠢的，但如果你坚持要这样做，那么你应该看一下一个可用的解析器，了解它的工作原理，并利用所学知识来构建自己的解析器。我建议你看看ANTLR。这至少会教你如何编写自己的语法。ANTLR将根据你的语法文件生成一个解析器，然后你可以以多种不同的方式使用解析器。生成的解析器可能会让你对如何编写自己的解析器有一些想法。祝你好运！ - JNYRanger

这是一个很好的示例，但你应该先开始支持 + - * /。在你实现了这部分之后（参考：http://alfasin.com/a-simple-calculator-in-ruby/），再计划如何扩展以支持指数和括号。 - Nir Alfasi

@JNYRanger：学习从来不会是愚蠢的，编写解析器是更好地理解编程语言的好方法。我不确定我是否会建议阅读解析器生成器的输出；它往往不太友好。 - Aasmund Eldhuset

@AasmundEldhuset 你说得非常正确，学习永远不会是愚蠢的。然而，重新发明轮子往往是无用的，但如果是为了教育目的，那么它就不是毫无意义的。通常情况下，我同意解析器生成器对人类不友好，但如果你使用简单的语法（例如在OP的问题中），ANTLR的输出代码却异常优雅。 - JNYRanger

@JNYRanger：有趣，我应该找时间了解一下ANTLR。当然，如果这是为某个生产系统，我同意使用解析器生成器，但从问题描述来看似乎不是这种情况。 - Aasmund Eldhuset

Answer 1

你应该了解一下Shunting Yard Algorithm，它可以帮助你解析包含运算符优先级和括号的代数表达式。

另外，你可能会对Abstract Syntax Trees感兴趣，它可以表示已解析表达式的结果，在此基础上可以进行进一步的操作，如美化输出和求值。

- NightRa

---

如果您是为了教育目的而做这个，我建议两种方法都尝试一下，但首先使用抽象语法树方法。Shunting Yard算法构建一个隐含的抽象语法树，然而在学习过程中，如果您可以看到显式的树并将其与预期的内容进行比较，则可能更容易调试/推理。另外，在代码中加入调试语句，以便您可以观察树的构建和使用过程也很酷。 - Morgen

Answer 2

你可能想要制作一个递归下降解析器，这是解析相对简单语言的标准方法。基本上，它是一种更有结构化的实现“查找括号并在其中评估表达式”的方法。但在开始之前，请确保您对递归操作感到舒适。

- Aasmund Eldhuset