如何为“（1 + 3 *（5/4））之类的字符串编写求值器并获得数值结果

这是一个面试问题我对它的解决方案感到困惑，我认为我需要堆栈来推送和弹出这些运算符和操作数，但是我需要两个堆栈，一个用于运算符，一个用于操作数？ 或者只是一个堆栈吗？我认为我们需要两个堆栈但是有没有办法解决使用一个堆栈？

我也有点困惑这将如何工作，每次我得到一个运算符我会弹出我的两个最顶层的操作数并将结果推入操作数堆栈

preferance首先是括号，然后是divide，multioply和last减法然后加法

但是如何检查何时弹出两个操作数并进行必要的关节操作？

Answer 1

看看调车场算法 。

分流码算法是一种解析中缀符号中指定的数学方程的方法。 它可用于以反向波兰表示法（RPN）或抽象语法树（AST）生成输出。 该算法由Edsger Dijkstra发明，并命名为“调车场”算法，因为其操作类似于铁路调车场。

Answer 2

您正在使用递归定义的结构解析表达式。 一个简单的选择是编写一个称为递归的正确解析器：

请参见http://en.wikipedia.org/wiki/Recursive_descent_parser

一旦你理解顶级“解析表达式”例程必须调用自己解析其组成表达式如EXPRESSION + EXPRESSION，它就是直截了当的。 你最终得到的是一个操作符节点树，其中包含操作数的表达式树。

你也可以使用像Bison这样的工具。 Bison是一个“编译器编译器”，它为给定语法的语言构建表驱动的解析器。 （Bison很老派：搜索“解析器生成器”了解更多信息。）

Answer 3

如果这是一个求职面试问题，正如原始海报所说的那样，那么候选人就不太可能会出现像分流码算法，递归下降解析器，将中缀转换为postfix 等所有内容。也许半个小时，把它拉下来。

不。他们可能正在测试你处理字符串之类的东西的能力，测试运算符{*，/，+， – }，左右括号，数字等等，并查看是否可以编写代码/伪代码来评估示例他们提供的表达，而不是一个全能的，全是舞蹈的应用程序。

另一方面，如果您想要一个如何为返回数值结果的字符串（如“（1 + 3 *（5/4））”编写求值程序的示例 ，这里有一些C ++ / Java示例 。

Answer 4

我使用boost精神解析器在很少的代码行中实现了这一点。 在各种情况下，它对我来说非常好。 （ http://spirit.sourceforge.net/ ）

详细说明：精神解析器允许您在标准BNC中构造语法并从表达式创建AST树 – 然后您可以轻松地遍历此树（在解释环境的情况下）并计算表达式。 精神和BNC的简短学习曲线将是必需的，但这肯定比滚动您自己的表达式评估者更容易

Answer 5

好。 它正在解析。 这是一项相当重要的工作……我的一个朋友写了一个非常令人印象深刻的程序，正是为了这个，打开一个变量方程式，所有都在OOP中。 井井有条。

基本上，列出运营商的订单，从括号开始。

找到最内部：搜索第一个）[关闭]然后从那里搜索第一个（[打开]。

现在你的内部短语没有括号。 现在搜索*例如，找到后面的数字和后面的数字，现在用它回答这个短语（例如514 * 354.25）。

这是最原始的做法..只是给了你一个开始。 对于重置你可能没有选择使用你的大脑：P

（如果你对我朋友的项目感兴趣就这么说）

Answer 6

此问题称为递归下降解析器。 可能还有其他forms的规范解决方案，我确信有 – 可能有几十种正确的方法。 David Eck在线发布了一个带有源代码和解释的递归下降解析器。 谷歌应该提供数以千计的有用资源，还应该关注dmoz和你最喜欢的搜索引擎。