c - 写表达式 : Infix, 后缀和前缀

Question

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

例如:

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

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

问题是:最好的方法是什么？(通过优化和验证)

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

我应该将表达式表示为树吗？如果是这样，我可以很容易地优化它(只需删除返回 0 或 smth 其他的节点)。

干杯，

Answer 1

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

如果你坚持自己写，

• 一个recursive descent parser可能是手工完成的最简单方法。
• 否则，您可以使用像 Bison 这样的工具(因为您正在使用 C 语言工作)。 This tutorial是我见过的最好的使用 Flex 和 Bison(或 Lex/Yacc)的方法

您还可以搜索 "expression evaluator"在 Codeproject 上——他们有很多关于该主题的文章。

前段时间我偶然发现了 M4 程序的表达式评估器。您可以研究其代码以了解其工作原理。我想this link在 Google Codesearch 上是我看到的版本。