algorithm - 具有优先级的方程(表达式)解析器？

Question

我使用简单的堆栈算法开发了一个方程解析器，该算法将处理二进制(+、-、|、&、*、/等)运算符、一元 (!) 运算符和括号。

但是，使用此方法后，所有内容都具有相同的优先级 - 无论运算符如何，它都是从左到右求值的，尽管可以使用括号强制执行优先级。

所以现在“1+11*5”返回 60，而不是预期的 56。

虽然这适用于当前项目，但我希望有一个通用例程可用于以后的项目。

为清晰起见进行了编辑:

什么是优先解析方程式的好算法？

我对一些易于实现的东西很感兴趣，并且明白我可以自己编写代码来避免可用代码的许可问题。

语法:

我不明白语法问题 - 我是手写的。它非常简单，我认为不需要 YACC 或 Bison。我只需要用诸如“2+3 * (42/13)”之类的方程来计算字符串。

语言:

我是用 C 来做的，但我对算法感兴趣，而不是特定于语言的解决方案。 C 语言足够低，因此在需要时很容易转换为另一种语言。

代码示例

我发布了 test code for the simple expression parser我上面说的。项目要求发生了变化，因此我从不需要针对性能或空间优化代码，因为它没有并入项目中。它是原始的冗长形式，应该很容易理解。如果我在运算符优先级方面进一步处理它，我可能会选择 the macro hack因为它与程序的其余部分简单匹配。不过，如果我在实际项目中使用它，我会选择更紧凑/更快速的解析器。

相关问题

Smart design of a math parser?

-亚当

Answer 1

shunting yard algorithm是正确的工具。维基百科对此真的很困惑，但基本上算法是这样工作的:

比如说，您想计算 1 + 2 * 3 + 4。凭直觉，您“知道”必须先计算 2 * 3，但您如何获得这个结果？关键是要意识到，当您从左到右扫描字符串时，您将在 后面 的运算符具有较低(或等于)优先级时评估运算符。在示例的上下文中，这是您想要执行的操作:

1. 看:1 + 2，什么都不做。
2. 现在看看 1 + 2 * 3，还是什么都不做。
3. 现在看看 1 + 2 * 3 + 4，现在您知道必须对 2 * 3 求值，因为下一个运算符的优先级较低。

你是如何实现的？

您想要两个堆栈，一个用于数字，另一个用于运算符。您一直将数字压入堆栈。您将每个新运算符与堆栈顶部的运算符进行比较，如果堆栈顶部的运算符具有更高的优先级，则将其从运算符堆栈中弹出，将操作数从数字堆栈中弹出，应用运算符并推送结果到数字堆栈上。现在您重复与栈顶运算符的比较。

回到这个例子，它是这样工作的:

N = [ ] 操作 = [ ]

• 读取 1。N = [1]，Ops = [ ]
• 阅读+。 N = [1], Ops = [+]
• 阅读 2。N = [1 2]，Ops = [+]
• 阅读*。 N = [1 2], Ops = [+ *]
• 阅读 3. N = [1 2 3]，Ops = [+ *]
• 阅读+。 N = [1 2 3]，运算 = [+ *]
  • 弹出 3, 2 并执行 2*3，并将结果压入 N。N = [1 6], Ops = [+]
  • + 是左关联的，因此您也想弹出 1、6 并执行 +。 N = [7]，操作数 = []。
  • 最后将 [+] 压入运算符堆栈。 N = [7]，Ops = [+]。
• 阅读 4。N = [7 4]。 Ops = [+].
• 你的输入已经用完了，所以你现在想清空堆栈。您将得到结果 11。

嗯，这并不难，不是吗？而且它不调用任何语法或解析器生成器。