c - 书写表达式：中缀、后缀和前缀

Question

我的任务是编写一个应用程序（不幸的是在 C 上），它以中缀表示法（使用变量、一元和二元运算符）读取表达式并将其存储在内存中，然后对其进行评估。此外，还应检查正确性。

例如：

3*(A+B)-(-2-78)*2+(0*A)

在我得到所有值之后，程序应该计算它。

问题是：最好的方法是什么？（优化和验证）

选择什么符号作为树的基础？

我应该将表达式表示为树吗？如果是这样，我可以轻松地对其进行优化（只需删除返回 0 或其他的节点）。

干杯，

Answer 1

Greg Hewgill 在上面的评论中建议的链接包含您需要的所有信息：

如果你坚持自己写，

• 递归下降解析器可能是最简单的手工方法。
• 否则，您可以使用 Bison 之类的工具（因为您使用的是 C 语言）。本教程是我见过的最好的使用 Flex 和 Bison（或 Lex/Yacc）的教程

您还可以在 Codeproject 上搜索“表达式评估器” ——他们有很多关于该主题的文章。

前段时间遇到了M4程序的表情评估器。你可以研究它的代码，看看它是如何工作的。我认为Google Codesearch 上的这个链接是我看到的版本。

Answer 2

您的问题暗示了对您的解决方案的要求：

不幸的是C

所以这里的一些建议可能是不允许的。尽管如此，我建议这是一个相当复杂的问题，你最好尝试找到一个合适的现有库，你可以将它链接到你的 C 代码中来为你做这件事。这可能会减少使代码正常工作所需的时间和精力，并减少正在进行的维护工作。当然，您必须考虑许可，但如果“外面”没有一个好的解析/评估库可以很好地解决这个问题，我会感到惊讶。