59

设计数学解析器最聪明的方法是什么？我的意思是一个接受数学字符串（如：“2 + 3 / 2 + (2 * 5)”）并返回计算值的函数？很久以前我确实在VB6中写过一个，但它最终变得臃肿而且不是很便携（或者就此而言很聪明......）。一般的想法，伪代码或真实代码表示赞赏。

4

10 回答 10

87

一个非常好的方法将涉及两个步骤。第一步包括将表达式从中缀转换为后缀（例如，通过Dijkstra 的 shunting yard）表示法。一旦完成，编写一个postfix evaluator就很简单了。

于 2008-09-22T12:37:46.677 回答
13

我写了几篇关于设计数学解析器的博客文章。有一个一般性的介绍、有关语法的基本知识、用 Ruby 编写的示例实现和一个测试套件。也许您会发现这些材料很有用。

于 2008-11-22T14:36:27.993 回答
6

你有几种方法。您可以生成动态代码并执行它以获得答案，而无需编写太多代码。只需在 .NET 中搜索运行时生成的代码，周围就有很多示例。

或者，您可以创建一个实际的解析器并生成一个小解析树，然后用于评估表达式。同样，这对于基本表达式来说非常简单。查看 codeplex，因为我相信他们那里有一个数学解析器。或者只是查找将包含示例的 BNF。任何介绍编译器概念的网站都会将此作为基本示例。

Codeplex 表达式评估器

于 2008-09-22T12:38:28.687 回答
4

如果你有一个“永远在线”的应用程序，只需将数学字符串发布到谷歌并解析结果。简单的方法，但不确定这是否是你所需要的——但我想在某种程度上很聪明。

于 2008-09-22T12:47:33.767 回答
4

我知道这很旧，但我在尝试开发一个计算器作为更大应用程序的一部分时遇到了这个问题，并使用公认的答案遇到了一些问题。这些链接对理解和解决这个问题非常有帮助，不应小看。我正在用 Java 编写一个 Android 应用程序，对于表达式“字符串”中的每个项目，当用户在键盘上键入时，我实际上将一个字符串存储在 ArrayList 中。对于中缀到后缀的转换，我遍历了 ArrayList 中的每个字符串，然后评估了新排列的字符串的后缀 ArrayList。这对于少数操作数/运算符来说非常棒，但更长的计算始终没有，尤其是当表达式开始计算为非整数时。在提供的中缀到后缀转换的链接中，如果扫描的项目是运算符并且 topStack 项目具有更高的优先级，则建议弹出堆栈。我发现这几乎是正确的。如果 topStack 项目的优先级高于或等于扫描的运算符，则弹出 topStack 项目最终使我的计算结果正确。希望这将有助于解决此问题的任何人，并感谢 Justin Poliey（和 fas？）提供了一些宝贵的链接。

于 2014-04-26T04:55:12.443 回答
3

相关问题Equation (expression) parser with priority? 也有一些关于如何开始的很好的信息。

-亚当

于 2008-09-22T12:57:15.913 回答
1

假设您的输入是字符串格式的中缀表达式，您可以将其转换为后缀，并使用一对堆栈：一个运算符堆栈和一个操作数堆栈，从那里解决解决方案。您可以在 Wikipedia 链接上找到一般算法信息。

于 2008-09-22T12:41:34.420 回答
1

ANTLR 是一个非常好的 LL(*) 解析器生成器。我强烈推荐它。

于 2008-12-31T14:14:27.110 回答
1

开发人员总是希望有一个干净的方法，并尝试从头开始实现解析逻辑，通常以Dijkstra Shunting-Yard 算法结束。结果是看起来很整洁的代码，但可能充满了错误。我已经开发了这样一个 API，JMEP，它可以完成所有这些，但是我花了很多年才拥有稳定的代码。

即使完成了所有这些工作，您甚至可以从那个项目页面中看到我正在认真考虑切换到使用 JavaCC 或 ANTLR，即使在所有工作已经完成之后也是如此。

于 2014-08-31T05:07:51.463 回答
1

从被问到这个问题的 11 年后：如果你不想重新发明轮子，那里有许多奇特的数学解析器。

我几年前写过一个，它支持算术运算、方程求解、微积分、积分、基本统计、函数/公式定义、绘图等。

它被称为ParserNG并且它是免费的。

评估表达式很简单：

    MathExpression expr = new MathExpression("(34+32)-44/(8+9(3+2))-22"); 
    System.out.println("result: " + expr.solve());

    result: 43.16981132075472

或者使用变量并计算简单的表达式：

 MathExpression expr = new MathExpression("r=3;P=2*pi*r;"); 
System.out.println("result: " + expr.getValue("P"));

或使用功能：

MathExpression expr = new MathExpression("f(x)=39*sin(x^2)+x^3*cos(x);f(3)"); 
System.out.println("result: " + expr.solve());

result: -10.65717648378352

或评估给定点的导数（注意它在幕后进行符号微分（不是数值），因此准确性不受数值近似误差的限制）：

MathExpression expr = new MathExpression("f(x)=x^3*ln(x); diff(f,3,1)"); 
System.out.println("result: " + expr.solve());

 result: 38.66253179403897

它在 x=3 处微分x^3 * ln(x)一次。您现在可以区分的次数是 1。

或数值积分：

MathExpression expr = new MathExpression("f(x)=2*x; intg(f,1,3)"); 
System.out.println("result: " + expr.solve());

result: 7.999999999998261... approx: 8

这个解析器速度相当快并且有很多其他的功能。

通过绑定到 Objective C 将它移植到 Swift 的工作已经结束，我们已经在其他迭代用例中使用它来绘制应用程序。

免责声明：ParserNG 由我编写。

于 2019-04-25T15:49:16.930 回答