代码之家 › 专栏 › 技术社区 › Rob P.

如何解析包含括号的数学表达式

parsing math .net

Rob P. · 技术社区 · 15 年前

这不是学校的作业,也不是什么,但我意识到这主要是个学术问题。但是,我一直在努力做的是分析“数学”文本,然后找到一个答案。

例如,我可以弄清楚如何解析“5+5”或“3*5”,但当我试图将操作正确地链接在一起时,却失败了。

(5+5)* 3

我实在搞不懂这件事,真是烦透了。如果有人能指点我一个方向,我会非常感激的。

编辑感谢所有的快速反应。很抱歉,我没有做更好的解释。

首先,我没有使用正则表达式。我也知道已经有一些库可以使用,作为一个字符串,一个数学表达式,并返回正确的值。所以,我主要看这个,因为,很遗憾,我没有“明白”。

第二-我所做的(可能是错误的),但我在计算“(和”),首先评估最深的项目。在简单的例子中,这是有效的;但是我的代码并不漂亮,而且更复杂的东西崩溃了。当我“计算”最低级别时,我正在修改字符串。

所以… (5+5)* 3

会变成 10×3

然后评估为三十

但这只是感觉“错了”。

我希望这有助于澄清问题。我当然会查看提供的链接。

11 回复 | 直到 8 年前

Matti Virkkunen 15 年前

很久以前,当我使用一个简单的图形应用程序时, this algorithm (对于这些简单的数学表达式来说,这是相当容易理解的,并且非常有用)首先将表达式转换为 RPN 然后计算结果。对于不同的变量值,RPN执行起来既好又快。

当然,语言解析是一个非常广泛的主题,有许多其他的方法来处理它(以及为它准备的工具)。

Andre Artus 15 年前

@冉冉升起的明星 [我希望将此添加为注释,但格式设置失败]

这似乎有违直觉,但二叉树既简单又灵活。在本例中,节点可以是常量(数字)或运算符。当您决定使用诸如控制流和函数之类的元素来扩展语言时,二叉树会使您的生活变得更加容易。

例子:

((3 + 4 - 1) * 5 + 6 * -7) / 2

                  '/'
                /     \
              +        2
           /     \
         *         *
       /   \     /   \
      -     5   6     -7
    /   \
   +     1
 /   \
3     4

在上述情况下,扫描器已被编程为将“-”后跟一系列数字作为单个数字,因此“-7”作为“数字”标记的值组件返回。-“后接空格”作为“减号”标记重新定义。这使得解析器更容易编写。它在需要“—(x*y)”的情况下失败,但您可以轻松地将表达式更改为“0-exp”

Andre Artus 15 年前

下面是一个简单的(简单的运算符优先顺序)语法。

expression = 
    term
    | expression "+" term
    | expression "-" term .
term = 
    factor
    | term "*" factor
    | term "/" factor .
factor = 
    number
    | "(" expression ")" .

当您处理“factor”时,您只需检查下一个标记是数字还是“(”,如果它是“(”,则再次分析“expression”,当表达返回检查下一个标记是否为”)。您可以通过使用 外面的 或裁判参数,或构建表达式树。

在ebnf中有同样的事情:

expression = 
    term
    { "+" term | "-" term  } .

term = 
    factor
    { "*" factor | "/" factor }.

factor = 
    number
    | "(" expression ")" .

jcolebrand 15 年前

你在学校上过正规语言课吗?实际上,您需要语法来进行分析。

编辑:哦,废话,维基百科说我错了,但现在我忘记了正确的名字:( http://en.wikipedia.org/wiki/Formal_grammar

Matt 15 年前

去年我写了一个基本的数学评估,原因是我记不清了。它在任何方面都不是一个“合适的”解析器,而且..就像所有的旧代码一样,我现在并不为此感到骄傲。

但是 you can take a look 看看它是否对你有帮助。

您通过启动这个来运行一些输入测试 standalone Java app

ChrisW 15 年前

当我想分析一些东西时,我决定使用黄金解析器:

自备文件(不需要书就能理解)
各种运行时引擎,使用各种编程语言,包括我想要的那种。

解析器包括 sample grammars 包括一个用于操作人员。

除了黄金之外,还有其他更著名的解析器,例如 ANTLR 我还没用过。

Community CDub 8 年前

选你, Code Golf: Mathematical expression evaluator (that respects PEMDAS)

Escualo 15 年前

正如许多答案已经说明的那样,问题是你需要 recursive parser 具有 associativity rules 因为你最终可以得到如下表达式:

val = (2-(2+4+(3-2)))/(2+1)*(2-1)

您的解析器需要知道:

插入式表达式是从内到外计算的。
除法优先于乘法(先除法,然后再乘以结果)
乘法优先于加减法。

正如您所能想象的,编写(好的)解析器是一门艺术。好的是有几个工具 parser generators 这使您可以轻松地定义语法你的语言, 解析规则 . 您可能需要检查维基百科中的条目 脑钠肽 ,以便您可以看到如何定义语法。

最后,如果你这样做是为了学习经验,那就继续吧。如果这是用于生产代码,不要重新设计轮子,并找到一个现有的库,否则您可能会花费1000行代码来添加2+2。

Community CDub 8 年前

本质上,您是在问我们如何编写一个“解析器”。下面是关于解析器的另一个堆栈溢出问题: hand coding a parser

Vivian River 15 年前

我做了一些和你描述的相似的事情。我使用递归来解析所有的括号。然后我使用三元树来表示不同的部分。左侧分支是操作员的左侧。中心分部是接线员。右分支是操作员的右侧。

简短回答 递归树和三元树。

Leroy Kegan 8 年前

始终可以选择使用数学分析器库,例如 mXparser . 你可以:

1-检查表达式语法

import org.mariuszgromada.math.mxparser.*;
...
...
Expression e = new Expression("2+3-");
e.checkSyntax();
mXparser.consolePrintln(e.getErrorMessage());

结果:

[mXparser-v.4.0.0] [2+3-] checking ...
[2+3-] lexical error 

Encountered "<EOF>" at line 1, column 4.
Was expecting one of:
    "(" ...
    "+" ...
    "-" ...
    <UNIT> ...
    "~" ...
    "@~" ...
    <NUMBER_CONSTANT> ...
    <IDENTIFIER> ...
    <FUNCTION> ...
    "[" ...

[2+3-] errors were found.

[MXParser-V.4.0.0]

2-评估表达式

import org.mariuszgromada.math.mxparser.*;
...
...
Expression e = new Expression("2+3-(10+2)");
mXparser.consolePrintln(e.getExpressionString() + " = " + e.calculate());

结果:

[mXparser-v.4.0.0] 2+3-(10+2) = -7.0

3-使用内置函数常量、运算符等。

import org.mariuszgromada.math.mxparser.*;
...
...
Expression e = new Expression("sin(pi)+e");
mXparser.consolePrintln(e.getExpressionString() + " = " + e.calculate());

结果:

[mXparser-v.4.0.0] sin(pi)+e = 2.718281828459045

4-定义自己的函数、参数和常量

import org.mariuszgromada.math.mxparser.*;
...
...
Argument z = new Argument("z = 10");
Constant a = new Constant("b = 2");
Function p = new Function("p(a,h) = a*h/2");
Expression e = new Expression("p(10, 2)-z*b/2", p, z, a);
mXparser.consolePrintln(e.getExpressionString() + " = " + e.calculate());

结果:

[mXparser-v.4.0.0] p(10, 2)-z*b/2 = 0.0

5-标记表达式字符串并使用表达式标记进行播放

import org.mariuszgromada.math.mxparser.*;
...
...
Argument x = new Argument("x");
Argument y = new Argument("y");
Expression e = new Expression("2*sin(x)+(3/cos(y)-e^(sin(x)+y))+10", x, y);
mXparser.consolePrintTokens( e.getCopyOfInitialTokens() );

结果:

[mXparser-v.4.0.0]  --------------------
[mXparser-v.4.0.0] | Expression tokens: |
[mXparser-v.4.0.0]  ---------------------------------------------------------------------------------------------------------------
[mXparser-v.4.0.0] |    TokenIdx |       Token |        KeyW |     TokenId | TokenTypeId |  TokenLevel |  TokenValue |   LooksLike |
[mXparser-v.4.0.0]  ---------------------------------------------------------------------------------------------------------------
[mXparser-v.4.0.0] |           0 |           2 |       _num_ |           1 |           0 |           0 |         2.0 |             |
[mXparser-v.4.0.0] |           1 |           * |           * |           3 |           1 |           0 |         NaN |             |
[mXparser-v.4.0.0] |           2 |         sin |         sin |           1 |           4 |           1 |         NaN |             |
[mXparser-v.4.0.0] |           3 |           ( |           ( |           1 |          20 |           2 |         NaN |             |
[mXparser-v.4.0.0] |           4 |           x |           x |           0 |         101 |           2 |         NaN |             |
[mXparser-v.4.0.0] |           5 |           ) |           ) |           2 |          20 |           2 |         NaN |             |
[mXparser-v.4.0.0] |           6 |           + |           + |           1 |           1 |           0 |         NaN |             |
[mXparser-v.4.0.0] |           7 |           ( |           ( |           1 |          20 |           1 |         NaN |             |
[mXparser-v.4.0.0] |           8 |           3 |       _num_ |           1 |           0 |           1 |         3.0 |             |
[mXparser-v.4.0.0] |           9 |           / |           / |           4 |           1 |           1 |         NaN |             |
[mXparser-v.4.0.0] |          10 |         cos |         cos |           2 |           4 |           2 |         NaN |             |
[mXparser-v.4.0.0] |          11 |           ( |           ( |           1 |          20 |           3 |         NaN |             |
[mXparser-v.4.0.0] |          12 |           y |           y |           1 |         101 |           3 |         NaN |             |
[mXparser-v.4.0.0] |          13 |           ) |           ) |           2 |          20 |           3 |         NaN |             |
[mXparser-v.4.0.0] |          14 |           - |           - |           2 |           1 |           1 |         NaN |             |
[mXparser-v.4.0.0] |          15 |           e |           e |           2 |           9 |           1 |         NaN |             |
[mXparser-v.4.0.0] |          16 |           ^ |           ^ |           5 |           1 |           1 |         NaN |             |
[mXparser-v.4.0.0] |          17 |           ( |           ( |           1 |          20 |           2 |         NaN |             |
[mXparser-v.4.0.0] |          18 |         sin |         sin |           1 |           4 |           3 |         NaN |             |
[mXparser-v.4.0.0] |          19 |           ( |           ( |           1 |          20 |           4 |         NaN |             |
[mXparser-v.4.0.0] |          20 |           x |           x |           0 |         101 |           4 |         NaN |             |
[mXparser-v.4.0.0] |          21 |           ) |           ) |           2 |          20 |           4 |         NaN |             |
[mXparser-v.4.0.0] |          22 |           + |           + |           1 |           1 |           2 |         NaN |             |
[mXparser-v.4.0.0] |          23 |           y |           y |           1 |         101 |           2 |         NaN |             |
[mXparser-v.4.0.0] |          24 |           ) |           ) |           2 |          20 |           2 |         NaN |             |
[mXparser-v.4.0.0] |          25 |           ) |           ) |           2 |          20 |           1 |         NaN |             |
[mXparser-v.4.0.0] |          26 |           + |           + |           1 |           1 |           0 |         NaN |             |
[mXparser-v.4.0.0] |          27 |          10 |       _num_ |           1 |           0 |           0 |        10.0 |             |
[mXparser-v.4.0.0]  ---------------------------------------------------------------------------------------------------------------

6-你可以在 mXparser tutorial , mXparser math collection 和 mXparser API definition .

7-MXParser支持:

爪哇
.NET/莫诺河
网络核心
.NET标准
.NET PCL
XAMARIN
西玛琳

最好的问候