关于算法：具有优先权的方程(表达式)解析器？

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

但是，使用这种方法会让我拥有相同优先级的所有内容 - 无论操作符如何，都会从左到右进行评估，尽管可以使用括号强制执行优先级。

所以现在"1 + 11 * 5"会返回60，而不是人们所期望的56。

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

编辑清晰：

解析具有优先级的方程的好算法是什么？

我对一些简单的实现感兴趣，并且理解我可以自己编写代码来避免使用可用代码的许可问题。

语法：

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

语言：

我在C中这样做，但我对算法感兴趣，而不是语言特定的解决方案。 C足够低，如果需要，很容易转换成另一种语言。

代码示例

我发布了上面讨论的简单表达式解析器的测试代码。项目要求发生了变化，因此我从不需要优化性能或空间代码，因为它没有包含在项目中。它是原始的详细形式，应该易于理解。如果我在运算符优先级方面做了更多的事情，我可能会选择宏hack，因为它简单地匹配程序的其余部分。但是，如果我在一个真实的项目中使用它，我将寻求一个更紧凑/更快速的解析器。

相关问题

Smart design of a math parser?

-亚当

调车场算法是适合此的工具。维基百科对此非常困惑，但基本上算法的工作原理如下：

比如说，你要评估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]，Ops = [+ *]
  • 弹出3,2并执行2 * 3，并将结果推到N. N = [1 6]，Ops = [+]
  • +是左关联的，因此你想要关闭1和6并执行+。 N = [7]，Ops = []。
  • 最后将[+]推到操作员堆栈上。 N = [7]，Ops = [+]。
• 阅读4. N = [7 4]。 Ops = [+]。
• 你输掉了输入，所以你现在要清空堆栈。你将得到结果11。

在那里，这不是那么困难，是吗？并且它不会调用任何语法或解析器生成器。

你想要一个递归下降解析器。

要获得优先权，您需要递归思考，例如，使用您的示例字符串，

要手动执行此操作，您必须阅读1，然后查看加号并从11开始一个全新的递归解析"会话"...并确保将11 * 5解析为自己的因子，产生一个1 + (11 * 5)的解析树。

即使尝试解释，这一切都感到非常痛苦，特别是在C的额外无能为力的情况下。在解析11之后，如果*实际上是+而不是，你将不得不放弃尝试制定一个术语而是解析11本身就是一个因素。我的脑袋已经爆炸了。这有可能采用递归的体面策略，但还有更好的方法......

简单(正确)的方式

如果您使用像Bison这样的GPL工具，您可能不需要担心许可问题，因为Bison生成的C代码不在GPL中(IANAL，但我很确定GPL工具不会强制使用GPL)生成代码/二进制文件;例如，Apple编译代码，例如Aperture与GCC，并且他们出售它而不必使用GPL代码)。

下载Bison(或类似的东西，ANTLR等)。

通常有一些示例代码可以运行bison并获得所需的C代码，演示这四个函数计算器：

http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html

查看生成的代码，看看这并不像听起来那么容易。此外，使用像Bison这样的工具的优点是1)你学到了一些东西(特别是如果你读了龙书并学习语法)，2)你避免NIH试图重新发明轮子。使用真正的解析器生成器工具，您实际上希望稍后扩展，向其他人展示解析器是解析工具的域。

更新：

这里的人提供了很多合理的建议。我反对跳过解析工具或仅使用Shunting Yard算法或手动滚动递归式解析器的唯一警告是，小型玩具语言有朝一日会变成具有函数(sin，cos，log)和变量，条件和for循环的大型实际语言。

对于一个简单的小型解释器来说，Flex / Bison可能会有点过分，但是当需要进行更改或需要添加功能时，一个解析器+评估器可能会导致故障。你的情况会有所不同，你需要用你的判断;只是不要为了你的罪而惩罚别人[2]并建立一个不够充分的工具。

我最喜欢的解析工具

世界上最好的工具是Parsec库(用于递归代码解析器)，它带有编程语言Haskell。它看起来很像BNF，或者像解析的一些专用工具或领域特定语言(示例代码[3])，但它实际上只是Haskell中的常规库，这意味着它在与其余的相同的构建步骤中编译你的Haskell代码，你可以编写任意Haskell代码并在你的解析器中调用它，你可以在同一个代码中混合和匹配其他库。 (顺便说一句，在Haskell之外的语言中嵌入这样的解析语言会导致语法残留。我在C＃中做了这个并且它运行得很好但是它不是那么漂亮和简洁。)

笔记：

1 Richard Stallman说，为什么你不应该使用Tcl

The principal lesson of Emacs is that
a language for extensions should not
be a mere"extension language". It
should be a real programming language,
designed for writing and maintaining
substantial programs. Because people
will want to do that!

[2]是的，我永远不会使用那种"语言"。

另外请注意，当我提交此条目时，预览是正确的，但是不太合适的解析器在第一段上吃了我的关闭锚标记，证明解析器不是一件小事，因为如果你使用正则表达式而且一个黑客攻击你可能会得到一些微妙而小的错误。

[3]使用Parsec的Haskell解析器的片段：一个四函数计算器，扩展了指数，括号，用于乘法的空格和常量(如pi和e)。

http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm

对不同方法的非常好的解释：

• 递归下降识别
• 调车场算法
• 经典的解决方案
• 优先攀登

用简单的语言和伪代码编写。

我喜欢'优先攀登'之一。

这里有一篇很好的文章，关于将简单的递归下降解析器与运算符优先级解析相结合。如果您最近一直在编写解析器，那么阅读它应该非常有趣和有益。

很久以前，我编写了自己的解析算法，在任何解析书中都找不到(比如Dragon Book)。看看Shunting Yard算法的指针，我确实看到了相似之处。

大约2年前，我在http://www.perlmonks.org/?node_id=554516上发了一篇关于Perl源代码的文章。移植到其他语言很容易：我做的第一个实现是在Z80汇编程序中。

它是使用数字直接计算的理想选择，但如果必须，可以使用它来生成解析树。

更新因为更多的人可以阅读(或运行)Javascript，所以在重新组织代码之后，我已经在Javascript中重新实现了我的解析器。整个解析器不到5k的Javascript代码(解析器大约100行，包装函数大约15行)，包括错误报告和注释。

您可以在http://users.telenet.be/bartl/expressionParser/expressionParser.html上找到现场演示。

如果您可以描述当前用于解析的语法，将会有所帮助。听起来问题可能就在那里！

编辑：

您不理解语法问题并且"您手动编写"的事实很可能解释了为什么您遇到"1 + 11 * 5"形式的表达式问题(即，运算符优先级) 。例如，谷歌搜索"算术表达式的语法"应该会产生一些好的指针。这样的语法不需要复杂：

例如，它可以做到这一点，并且可以通过简单的增强来处理一些更复杂的表达式(包括例如函数或幂，......)。

我建议你看看这个帖子，例如。

几乎所有语法/解析的介绍都以算术表达式为例。

请注意，使用语法并不意味着使用特定工具(la yacc，Bison，...)。实际上，你肯定已经使用了以下语法：

(或类似的东西)不知道它！

你有没有想过使用Boost Spirit？它允许你用C ++编写类似EBNF的语法，如下所示：

当你提出问题时，不需要任何递归。答案是三件事：Postfix符号加Shunting Yard算法加Postfix表达式评估：

1)。 Postfix符号=发明以消除对显式优先级规范的需要。在网上阅读更多内容，但这里是它的要点：中缀表达式(1 + 2)* 3，同时人们很容易阅读和处理通过机器计算效率不高。什么是？简单的规则，即"通过优先级缓存重写表达式，然后始终从左到右处理"。因此，中缀(1 + 2)* 3成为后缀12 + 3 *。 POST因为操作符总是放在操作数之后。

2)。评估后缀表达式。简单。从后缀字符串中读取数字。将它们推到堆叠上直到看到操作员。检查操作员类型 - 一元吗？二进制？第三？根据需要弹出尽可能多的操作数以评估此运算符。评估。将结果推回堆栈！而你几乎完成了。继续这样做，直到堆栈只有一个条目=值u r寻找。

让我们做(1 + 2)* 3，后缀是"12 + 3 *"。读取第一个数字= 1.将其推入堆栈。读下一个。 Number = 2.将其推入堆栈。读下一个。操作员。哪一个？ +。哪一种？二进制=需要两个操作数。弹出堆栈两次= argright为2，argleft为1. 1 + 2为3.将3推回堆栈。从postfix字符串开始阅读。它的数量。 3.Push。读下一个。操作员。哪一个？ *。哪一种？ Binary =需要两个数字 - > pop stack两次。首先进入argright，第二次进入argleft。评估操作 - 3次3是9.Push 9在堆栈上。阅读下一个postfix char。它是空的。输入结束。 Pop stack onec =这是你的答案。

3)。 Shunting Yard用于将人(易)可读的中缀表达式转换为后缀表达式(在某些练习后人类也很容易阅读)。易于手动编码。见上面的评论和网。

我在PIClist上找到了关于Shunting Yard算法的信息：

Harold writes:

I remember reading, a long time ago, of an algorithm that converted
algebraic expressions to RPN for easy evaluation. Each infix value or
operator or parenthesis was represented by a railroad car on a
track. One
type of car split off to another track and the other continued straight
ahead. I don't recall the details (obviously!), but always thought it
would be interesting to code. This is back when I was writing 6800 (not
68000) assembly code.

这是"调车场algorythm"
它是大多数机器解析器
采用。请参阅有关解析的文章
维基百科。一种简单的编码方式
调车场algorythm是用两个
栈。一个是"推"堆栈和
另一个是"减少"或"结果"
堆。例：

pstack =()//空rstack =()
输入：1 + 2 * 3优先级= 10 //最低
reduce = 0 //不要减少

start：token'1'：isnumber，put in
pstack(push)token'+'：isoperator
如果优先级<，则设置优先级= 2 previous_operator_precedence然后 reduce()//见下面把'+'放进去 pstack(push)token'2'：isnumber， 放入pstack(推)令牌'*'： isoperator，set precedence = 1，put in pstack(push)//检查优先级为 //上面标记'3'：isnumber，放入 pstack(推)输入结束，需要 reduce(目标是空的pstack)reduce() //完成

从推动中减少，弹出元素
堆叠并将它们放入结果中
堆栈，始终交换前2项
如果它们是形式的pstack
'运营商''号码'：

pstack：'1''+'''''''3'rstack :()
... pstack :()rstack：'3''2''''1'
'+'

如果表达式是：

1 * 2 + 3

然后减少触发器会有
一直在阅读令牌'+'
其中的比例低于
'*'已被推，所以它会有
完成：

pstack：'1''''2'rstack :()...
pstack :()rstack：'1''2'''

然后按'+'然后按'3'和
然后终于减少：

pstack：'+''3'rstack：'1''2'''
...... pstack :()rstack：'1''2''''3'
'+'

所以简短的版本是：推送数字，
当推动操作员检查
前一个运算符的优先级。
如果它高于运营商的
首先，现在要推动
减少，然后推动电流
运营商。处理parens只需保存
'previous'的优先顺序
操作员，并在pstack上加上标记
告诉减少algorythm
解决内部时停止减少
一对父母。闭幕式
最终会触发减少
输入，并删除打开
来自pstack的paren mark，和
恢复'上一次操作'
优先级，因此解析可以继续
在它离开后关闭的paren之后
关闭。这可以通过递归来完成
或没有(提示：使用堆栈存储
以前的优先顺序
遇到'('...)。该
这是一般化的使用方法
一个解析器生成器实现
shunting yard algorythm，f.ex。运用
yacc或bison或taccle(tcl类似的
YACC)。

彼得

-亚当

---

你想用一种语言吗？ ANTLR将允许您从Java角度执行此操作。 Adrian Kuhn对如何在Ruby中编写可执行语法有很好的写作;事实上，他的例子几乎就是你的算术表达式例子。

---

这取决于你想要它的"一般"程度。

如果你想要它真的非常普遍，比如能够像sin(4 + 5)* cos(7 ^ 3)一样解析数学函数，你可能需要一个解析树。

其中，我认为完整的实现不适合粘贴在这里。我建议你看一下臭名昭着的"龙书"。

但是如果你只是想要优先支持，那么你可以通过首先将表达式转换为postfix形式来实现这一点，其中你可以从谷歌获得可以复制和粘贴的算法，或者我认为你可以用二进制文件自己编写代码树。

如果你有postfix形式，那么从那时起它就是一块蛋糕，因为你已经了解了堆栈的帮助。

---

我在我的网站上发布了一个超紧凑(1类，<10 KiB)Java数学评估器的源代码。这是一种类型的递归下降解析器，它引起了接受答案的海报的颅爆炸。

它支持完整优先级，括号，命名变量和单参数函数。

---

我建议作弊并使用Shunting Yard算法。这是编写简单的计算器类型解析器的简单方法，并且优先考虑。

如果你想正确地标记事物并且有变量等涉及那么我会继续按照其他人的建议写一个递归下降解析器，但是如果你只需要一个计算器式解析器那么这个算法就足够了:-)

---

我根据Apache License 2.0的条款发布了基于Dijkstra的Shunting Yard算法的表达式解析器：

http://projects.congrace.de/exp4j/index.html

---

优先解析的另一个资源是维基百科上的运算符优先解析器条目。涵盖Dijkstra的分流码算法和树替代算法，但更值得注意的是涵盖了一个非常简单的宏替换算法，可以在任何优先无知解析器前面轻松实现：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

#include <stdio.h> int main(int argc, char *argv[]){   printf("((((");   for(int i=1;i!=argc;i++){     if(argv[i] && !argv[i][1]){       switch(argv[i]){       case '^': printf(")^("); continue;       case '*': printf("))*(("); continue;       case '/': printf("))/(("); continue;       case '+': printf(")))+((("); continue;       case '-': printf(")))-((("); continue;       }     }     printf("%s", argv[i]);   }   printf(")))) ");   return 0; }

将其调用为：

1 2 3

$ cc -o parenthesise parenthesise.c $ ./parenthesise a \* b + c ^ d / e ((((a))*((b)))+(((c)^(d))/((e))))

它的简洁性非常棒，而且非常容易理解。

---

我在MathEclipse Parser项目中用Java实现了一个递归下降解析器。它也可以用作Google Web Toolkit模块

---

我在F＃中写了一个表达式解析器，并在这里写了博客。它使用了分流码算法，但不是从中缀转换为RPN，而是添加了第二个堆栈来累积计算结果。它正确处理运算符优先级，但不支持一元运算符。我写这篇文章是为了学习F＃，不是为了学习表达式解析。

---

可以在此处找到使用pyparsing的Python解决方案。使用具有优先级的各种运算符解析中缀表示法是相当常见的，因此pyparsing还包括infixNotation(以前的operatorPrecedence)表达式构建器。有了它，您可以使用"AND"，"OR"，"NOT"轻松定义布尔表达式。或者您可以扩展您的四函数算术以使用其他运算符，例如！对于阶乘，或'％'表示模数，或添加P和C运算符来计算排列和组合。你可以为矩阵表示法编写一个中缀解析器，包括处理'-1'或'T'运算符(用于反转和转置)。 4函数解析器的operatorPrecedence示例(带有'！'以获得乐趣)在这里，一个功能更全面的解析器和求值器就在这里。

---

我目前正在撰写一系列文章，构建一个正则表达式解析器，作为设计模式和可读编程的学习工具。你可以看看可读代码。本文明确使用了分流码算法。

---

我知道这是一个迟到的答案，但我刚刚写了一个小的解析器，允许所有运算符(前缀，后缀和中缀左，中缀右和非关联)具有任意优先级。

我将扩展它以支持任意DSL支持的语言，但我只是想指出一个人不需要自定义解析器来实现运算符优先级，可以使用根本不需要表的通用解析器，以及只查看每个运算符的优先级。人们一直在提到可以接受非法输入的自定义Pratt解析器或分流码解析器 - 这个不需要定制，并且(除非有错误)不接受错误的输入。它在某种意义上是不完整的，它是为了测试算法而编写的，它的输入是一种需要一些预处理的形式，但有一些注释可以说清楚。

注意一些常见类型的运算符缺失，例如用于索引的运算符类型，即table [index]或调用函数函数(parameter-expression，...)
我将添加这些，但将两者都视为后缀运算符，其中在分隔符'['和']'或'('和')'之间的内容使用表达式解析器的不同实例进行解析。很抱歉离开了，但后缀部分是 - 添加其余的可能几乎是代码大小的两倍。

由于解析器只有100行的球拍代码，或许我应该将它粘贴在这里，我希望这不会超过stackoverflow允许的。

有关任意决定的一些细节：

如果低优先级后缀运算符竞争与低优先级前缀运算符相同的中缀块，则前缀运算符获胜。这在大多数语言中都没有出现，因为大多数语言都没有低优先级的后缀运算符。
- 例如：((数据a)(左1 +)(前2没有)(数据b)(后3！)(左1 +)(数据c))
是+不是b！+ c其中not是前缀运算符而且！是后缀运算符，两者都有较低的
优先级高于+所以他们希望以不兼容的方式分组为
(a +不是b！)+ c
或者作为
a +(不是b！+ c)
在这些情况下，前缀运算符总是获胜，所以第二种是它解析的方式

非关联中缀运算符确实存在，因此您不必假装返回不同类型的运算符一起使用，但没有不同的表达类型，每个运算符都是kludge。因此，在该算法中，非关联运算符拒绝不仅与自身关联，而且与任何具有相同优先级的运算符关联。这是一种常见的情况，因为<= ==> = etc在大多数语言中都不会相互关联。

关于不同类型的运算符(左，前缀等)如何在优先级上打破关系的问题是不应该出现的问题，因为给不同类型的运算符赋予相同的优先级实际上没有意义。这种算法在这些情况下做了一些事情，但我甚至都不打算弄清楚究竟是什么，因为这样的语法首先是一个坏主意。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120

#lang racket ;cool the algorithm fits in 100 lines! (define MIN-PREC -10000) ;format (pre prec name) (left prec name) (right prec name) (nonassoc prec name) (post prec name) (data name) (grouped exp) ;for example"not a*-7+5 < b*b or c >= 4" ;which groups as: not ((((a*(-7))+5) < (b*b)) or (c >= 4))" ;is represented as '((pre 0 not)(data a)(left 4 *)(pre 5 -)(data 7)(left 3 +)(data 5)(nonassoc 2 <)(data b)(left 4 *)(data b)(right 1 or)(data c)(nonassoc 2 >=)(data 4)) ;higher numbers are higher precedence ;"(a+b)*c" is represented as ((grouped (data a)(left 3 +)(data b))(left 4 *)(data c)) (struct prec-parse ([data-stack #:mutable #:auto]                     [op-stack #:mutable #:auto])   #:auto-value '()) (define (pop-data stacks)   (let [(data (car (prec-parse-data-stack stacks)))]     (set-prec-parse-data-stack! stacks (cdr (prec-parse-data-stack stacks)))     data)) (define (pop-op stacks)   (let [(op (car (prec-parse-op-stack stacks)))]     (set-prec-parse-op-stack! stacks (cdr (prec-parse-op-stack stacks)))     op)) (define (push-data! stacks data)     (set-prec-parse-data-stack! stacks (cons data (prec-parse-data-stack stacks)))) (define (push-op! stacks op)     (set-prec-parse-op-stack! stacks (cons op (prec-parse-op-stack stacks)))) (define (process-prec min-prec stacks)   (let [(op-stack (prec-parse-op-stack stacks))]     (cond ((not (null? op-stack))            (let [(op (car op-stack))]              (cond ((>= (cadr op) min-prec)                     (apply-op op stacks)                     (set-prec-parse-op-stack! stacks (cdr op-stack))                     (process-prec min-prec stacks)))))))) (define (process-nonassoc min-prec stacks)   (let [(op-stack (prec-parse-op-stack stacks))]     (cond ((not (null? op-stack))            (let [(op (car op-stack))]              (cond ((> (cadr op) min-prec)                     (apply-op op stacks)                     (set-prec-parse-op-stack! stacks (cdr op-stack))                     (process-nonassoc min-prec stacks))                    ((= (cadr op) min-prec) (error"multiply applied non-associative operator"))                    )))))) (define (apply-op op stacks)   (let [(op-type (car op))]     (cond ((eq? op-type 'post)            (push-data! stacks `(,op ,(pop-data stacks) )))           (else ;assume infix            (let [(tos (pop-data stacks))]              (push-data! stacks `(,op ,(pop-data stacks) ,tos))))))) (define (finish input min-prec stacks)   (process-prec min-prec stacks)   input   ) (define (post input min-prec stacks)   (if (null? input) (finish input min-prec stacks)       (let* [(cur (car input))              (input-type (car cur))]         (cond ((eq? input-type 'post)                (cond ((< (cadr cur) min-prec)                       (finish input min-prec stacks))                      (else                       (process-prec (cadr cur)stacks)                       (push-data! stacks (cons cur (list (pop-data stacks))))                       (post (cdr input) min-prec stacks))))               (else (let [(handle-infix (lambda (proc-fn inc)                                           (cond ((< (cadr cur) min-prec)                                                  (finish input min-prec stacks))                                                 (else                                                  (proc-fn (+ inc (cadr cur)) stacks)                                                  (push-op! stacks cur)                                                  (start (cdr input) min-prec stacks)))))]                       (cond ((eq? input-type 'left) (handle-infix process-prec 0))                             ((eq? input-type 'right) (handle-infix process-prec 1))                             ((eq? input-type 'nonassoc) (handle-infix process-nonassoc 0))                             (else error"post op, infix op or end of expression expected here")))))))) ;alters the stacks and returns the input (define (start input min-prec stacks)   (if (null? input) (error"expression expected")       (let* [(cur (car input))              (input-type (car cur))]         (set! input (cdr input))         ;pre could clearly work with new stacks, but could it reuse the current one?         (cond ((eq? input-type 'pre)                (let [(new-stack (prec-parse))]                  (set! input (start input (cadr cur) new-stack))                  (push-data! stacks                              (cons cur (list (pop-data new-stack))))                  ;we might want to assert here that the cdr of the new stack is null                  (post input min-prec stacks)))               ((eq? input-type 'data)                (push-data! stacks cur)                (post input min-prec stacks))               ((eq? input-type 'grouped)                (let [(new-stack (prec-parse))]                  (start (cdr cur) MIN-PREC new-stack)                  (push-data! stacks (pop-data new-stack)))                ;we might want to assert here that the cdr of the new stack is null                (post input min-prec stacks))               (else (error"bad input")))))) (define (op-parse input)   (let [(stacks (prec-parse))]     (start input MIN-PREC stacks)     (pop-data stacks))) (define (main)   (op-parse (read))) (main)

---

这是一个用Java编写的简单案例递归解决方案。请注意，它不处理负数但您可以添加，如果您想：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

public class ExpressionParser { public double eval(String exp){     int bracketCounter = 0;     int operatorIndex = -1;     for(int i=0; i<exp.length(); i++){         char c = exp.charAt(i);         if(c == '(') bracketCounter++;         else if(c == ')') bracketCounter--;         else if((c == '+' || c == '-') && bracketCounter == 0){             operatorIndex = i;             break;         }         else if((c == '*' || c == '/') && bracketCounter == 0 && operatorIndex < 0){             operatorIndex = i;         }     }     if(operatorIndex < 0){         exp = exp.trim();         if(exp.charAt(0) == '(' && exp.charAt(exp.length()-1) == ')')             return eval(exp.substring(1, exp.length()-1));         else             return Double.parseDouble(exp);     }     else{         switch(exp.charAt(operatorIndex)){             case '+':                 return eval(exp.substring(0, operatorIndex)) + eval(exp.substring(operatorIndex+1));             case '-':                 return eval(exp.substring(0, operatorIndex)) - eval(exp.substring(operatorIndex+1));             case '*':                 return eval(exp.substring(0, operatorIndex)) * eval(exp.substring(operatorIndex+1));             case '/':                 return eval(exp.substring(0, operatorIndex)) / eval(exp.substring(operatorIndex+1));         }     }     return 0; }

}

---

算法可以很容易地在C中编码为递归下降解析器。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

#include <stdio.h> #include <ctype.h> /*  *  expression -> sum  *  sum -> product | product"+" sum  *  product -> term | term"*" product  *  term -> number | expression  *  number -> [0..9]+  */ typedef struct {     int value;     const char* context; } expression_t; expression_t expression(int value, const char* context) {     return (expression_t) { value, context }; } /* begin: parsers */ expression_t eval_expression(const char* symbols); expression_t eval_number(const char* symbols) {     // number -> [0..9]+     double number = 0;             while (isdigit(*symbols)) {         number = 10 * number + (*symbols - '0');         symbols++;     }     return expression(number, symbols); } expression_t eval_term(const char* symbols) {     // term -> number | expression     expression_t number = eval_number(symbols);     return number.context != symbols ? number : eval_expression(symbols); } expression_t eval_product(const char* symbols) {     // product -> term | term"*" product     expression_t term = eval_term(symbols);     if (*term.context != '*')         return term;     expression_t product = eval_product(term.context + 1);     return expression(term.value * product.value, product.context); } expression_t eval_sum(const char* symbols) {     // sum -> product | product"+" sum     expression_t product = eval_product(symbols);     if (*product.context != '+')         return product;     expression_t sum = eval_sum(product.context + 1);     return expression(product.value + sum.value, sum.context); } expression_t eval_expression(const char* symbols) {     // expression -> sum     return eval_sum(symbols); } /* end: parsers */ int main() {     const char* expression ="1+11*5";     printf("eval("%s") == %d ", expression, eval_expression(expression).value);     return 0; }

_{next libs可能有用：
yupana - 严格算术运算;
tinyexpr - 算术运算+ C数学函数+用户提供的函数;
mpc - 解析器组合器}

说明

让我们捕捉代表代数表达式的符号序列。
第一个是数字，即重复一次或多次的十进制数字。
_{我们将这种表示法称为生产规则。}

1	number -> [0..9]+

添加运算符及其操作数是另一个规则。
它是number或代表sum"*" sum序列的任何符号。

1	sum -> number | sum"+" sum

尝试将number替换为sum"+" sum ，然后sum"+" sum可以扩展为[0..9]+"+" [0..9]+，最终可以缩小为1+8，这是正确的加法表达式。

其他替换也将产生正确的表达式：sum"+" sum - > number"+" sum - > number"+" sum"+" sum - > number"+" sum"+" number - > number"+" number"+" number - > 12+3+5

我们可以一点一点地使用表达所有可能的代数表达式的生成规则 _{aka grammar 。}

1 2 3 4 5 6 7

expression -> sum sum -> difference | difference"+" sum difference -> product | difference"-" product product -> fraction | fraction"*" product fraction -> term | fraction"/" term term ->"(" expression")" | number number -> digit+

控制运算符优先级更改其生产规则相对于其他人的位置。查看上面的语法并注意*的生成规则放在+以下，这将强制product在sum之前进行评估。
实施只是将模式识别与评估相结合，从而与生产规则密切相关。

1 2 3 4 5 6 7 8 9

expression_t eval_product(const char* symbols) {     // product -> term | term"*" product     expression_t term = eval_term(symbols);     if (*term.context != '*')         return term;     expression_t product = eval_product(term.context + 1);     return expression(term.value * product.value, product.context); }

这里我们首先评估term，如果在_{之后没有*字符，则返回它，否则在我们的生产规则中选择否则 - 在之后评估符号并返回term.value * product.value 这是正确选择我们的生产规则，即term"*" product}

---