具有优先级的等式（表达式）解析器？

我使用一个简单的堆栈算法开发了一个方程式解析器，该算法将处理二元（+， – ，|，＆，*，/等）运算符，一元（！）运算符和括号。

然而，使用这种方法，我会留下所有具有相同优先级的东西 – 无论运算符如何，都会从左向右进行评估，但优先级可以使用括号来强制执行。

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

虽然这是适合当前的项目，我想有一个通用的例程，我可以用于以后的项目。

为清晰起见编辑：

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

我感兴趣的是一些简单的实现和理解，我可以自己编码，以避免授权问题与可用的代码。

语法：

我不明白这个语法问题 – 我手写的。 这很简单，我没有看到YACC或野牛的需要。 我只需要用“2 + 3 *（42/13）”这样的等式来计算字符串。

语言：

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

代码示例

我发布了我上面提到的简单表达式解析器的测试代码 。 项目需求改变了，所以我从来不需要优化性能或空间的代码，因为它没有被纳入到项目中。 这是在原来的冗长的形式，应该是容易理解的。 如果我在运算符优先级方面做了进一步处理，我可能会选择这个宏，因为它与简单程序的其余部分相匹配。 如果我曾经在一个真实的项目中使用过这个功能，那么我会选择一个更紧凑，更快速的解析器。

相关的问题

数学解析器的智能设计？

-亚当

Answer 1

困难的方式

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

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

1+11*5 

要做这个手动，你将不得不阅读1 ，然后看到加号，并开始一个全新的递归解析“会议”从11开始……并确保解析11 * 5到自己的因素，产生一个解析树1 + (11 * 5) 。

这一切都感到非常痛苦，甚至试图解释，特别是与增加了无能为力C.看到，在解析11后，如果*实际上是一个+而不是，你将不得不放弃尝试做出一个术语，而是解析11本身就是一个因素。 我的头已经爆炸了。 这是可能的递归体面战略，但有一个更好的办法…

简单（正确）的方法

如果您使用像Bison这样的GPL工具，那么您可能不需要担心授权问题，因为由bison生成的C代码不在GPL范围内（IANAL，但是我确信GPL工具不会强制GPL生成的代码/二进制文件;例如苹果公司编译的代码就像说，与GCC光圈，他们出售，而不需要GPL代码）。

下载野牛 （或类似的东西，ANTLR等）。

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

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

看看生成的代码，看看这不像听起来那么简单。 另外，使用像Bison这样的工具的好处是：1）你学到了一些东西（尤其是如果你阅读龙书并学习语法），2）避免NIH试图重新发明轮子。 使用真正的解析器生成器工具，您实际上有望在稍后扩展，向其他人展示解析器是解析工具的领域。

---

更新：

这里的人们提供了很多合理的建议。 对于跳过解析工具或仅使用Shunting Yard算法或手卷递归正确的解析器，我唯一的警告是，有一点玩具语言¹可能有一天变成具有函数（sin，cos，log）和变量，条件的大型实际语言，循环。

对于一个简单的解释器来说，Flex / Bison可能是一个过分的矫枉过正的问题，但是当需要进行更改或者需要添加特性时，一个解析器+评估器可能会引起麻烦。 你的情况会有所不同，你需要使用你的判断; 只是不要惩罚别人为你的罪 ^[2]，并建立一个不够的工具。

我最喜欢的解析工具

世界上最好的工具是用于编程语言Haskell的Parsec库（用于递归裁剪）。 它看起来很像BNF ，或者像一些专门用于解析的工具或领域专用语言（示例代码[3]），但实际上它只是Haskell中的一个常规库，意味着它与其他构建步骤一样编译的Haskell代码，你可以编写任意的Haskell代码并在解析器中调用它，并且可以在同一代码中混合和匹配其他库。 （用Haskell以外的语言嵌入这样的解析语言会导致大量的语法错误，我在C＃中做了这样的工作，效果很好，但不是很漂亮和简洁。

笔记：

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

Emacs的主要教训是扩展语言不应该只是一个“扩展语言”。 它应该是一个真正的编程语言，旨在编写和维护大量的程序。 因为人们会想这样做！

[2]是的，我永远因使用这种“语言”而伤痕累累。

另外请注意，当我提交这个条目时，预览是正确的，但是SO不足以解析我的第一段的关闭锚标签 ，证明解析器不会被嘲笑，因为如果你使用正则表达式， 可能会得到一些细微的错误 。

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

 aexpr = expr `chainl1` toOp expr = optChainl1 term addop (toScalar 0) term = factor `chainl1` mulop factor = sexpr `chainr1` powop sexpr = parens aexpr <|> scalar <|> ident powop = sym "^" >>= return . (B Pow) <|> sym "^-" >>= return . (\xy -> B Pow x (B Sub (toScalar 0) y)) toOp = sym "->" >>= return . (B To) mulop = sym "*" >>= return . (B Mul) <|> sym "/" >>= return . (B Div) <|> sym "%" >>= return . (B Mod) <|> return . (B Mul) addop = sym "+" >>= return . (B Add) <|> sym "-" >>= return . (B Sub) scalar = number >>= return . toScalar ident = literal >>= return . Lit parens p = do lparen result <- p rparen return result 

Answer 2

调车场算法是正确的工具。 维基百科对此很困惑，但基本上这个算法是这样的：

说，你要评估1 + 2 * 3 + 4.直觉上，你“知道”你必须先做2 * 3，但你怎么得到这个结果呢？ 关键是要认识到，当你从左到右扫描字符串时，你会评估一个操作符，当它后面的操作符具有较低（或相等）的优先顺序。 在这个例子的背景下，这是你想要做的：

1. 看：1 + 2，不要做任何事情。
2. 现在看1 + 2 * 3，还是不要做任何事情。
3. 现在看看1 + 2 * 3 + 4，现在你知道2 * 3必须被评估，因为下一个运算符的优先级较低。

你如何实现这个？

你想有两个堆栈，一个用于数字，另一个用于操作员。 你总是把数字推到堆栈上。 比较每个新的操作符与堆栈顶部的操作符，如果堆栈顶部的操作符具有更高的优先级，则将其从操作堆栈弹出，将操作数从数字堆栈中弹出，应用操作员并推送结果到数字堆栈上。 现在你重复一下堆栈操作符的顶部的比较。

回到这个例子，它的工作原理是这样的：

N = [] Ops = []

• 阅读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 = [+ *]
  • Pop 3，2并执行2 * 3，并将结果推送到N. N = [1 6]，Ops = [+]
  • +是左结合的，所以你想要弹出1,6关闭，并执行+。 N = [7]，Ops = []。
  • 最后将[+]推到操作员堆栈上。 N = [7]，Ops = [+]。
• 阅读4. N = [7 4]。 Ops = [+]。
• 您的输入已经耗尽，所以您现在需要清空堆栈。 你将得到结果11。

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

Answer 3

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

很好的解释不同的方法：

• 递归下降识别
• 分流码算法
• 经典的解决方案
• 优先攀登

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

我喜欢“优先攀登”一个。

Answer 4

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

Answer 5

很久以前，我编写了自己的解析算法，在任何有关解析的书籍中都找不到（比如龙书）。 看看Shunting Yard算法的指针，我确实看到了相似之处。

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

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

更新因为更多的人可以阅读（或运行）的Javascript，我已经重新实现了我的解析器在Javascript中，代码已经重组。 整个解析器是在Javascript代码5K以下（解析器约100行，包装函数15行），包括错误报告和注释。

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

 // operator table var ops = { '+' : {op: '+', precedence: 10, assoc: 'L', exec: function(l,r) { return l+r; } }, '-' : {op: '-', precedence: 10, assoc: 'L', exec: function(l,r) { return lr; } }, '*' : {op: '*', precedence: 20, assoc: 'L', exec: function(l,r) { return l*r; } }, '/' : {op: '/', precedence: 20, assoc: 'L', exec: function(l,r) { return l/r; } }, '**' : {op: '**', precedence: 30, assoc: 'R', exec: function(l,r) { return Math.pow(l,r); } } }; // constants or variables var vars = { e: Math.exp(1), pi: Math.atan2(1,1)*4 }; // input for parsing // var r = { string: '123.45+33*8', offset: 0 }; // r is passed by reference: any change in r.offset is returned to the caller // functions return the parsed/calculated value function parseVal(r) { var startOffset = r.offset; var value; var m; // floating point number // example of parsing ("lexing") without aid of regular expressions value = 0; while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++; if(r.string.substr(r.offset, 1) == ".") { r.offset++; while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++; } if(r.offset > startOffset) { // did that work? // OK, so I'm lazy... return parseFloat(r.string.substr(startOffset, r.offset-startOffset)); } else if(r.string.substr(r.offset, 1) == "+") { // unary plus r.offset++; return parseVal(r); } else if(r.string.substr(r.offset, 1) == "-") { // unary minus r.offset++; return negate(parseVal(r)); } else if(r.string.substr(r.offset, 1) == "(") { // expression in parens r.offset++; // eat "(" value = parseExpr(r); if(r.string.substr(r.offset, 1) == ")") { r.offset++; return value; } r.error = "Parsing error: ')' expected"; throw 'parseError'; } else if(m = /^[a-z_][a-z0-9_]*/i.exec(r.string.substr(r.offset))) { // variable/constant name // sorry for the regular expression, but I'm too lazy to manually build a varname lexer var name = m[0]; // matched string r.offset += name.length; if(name in vars) return vars[name]; // I know that thing! r.error = "Semantic error: unknown variable '" + name + "'"; throw 'unknownVar'; } else { if(r.string.length == r.offset) { r.error = 'Parsing error at end of string: value expected'; throw 'valueMissing'; } else { r.error = "Parsing error: unrecognized value"; throw 'valueNotParsed'; } } } function negate (value) { return -value; } function parseOp(r) { if(r.string.substr(r.offset,2) == '**') { r.offset += 2; return ops['**']; } if("+-*/".indexOf(r.string.substr(r.offset,1)) >= 0) return ops[r.string.substr(r.offset++, 1)]; return null; } function parseExpr(r) { var stack = [{precedence: 0, assoc: 'L'}]; var op; var value = parseVal(r); // first value on the left for(;;){ op = parseOp(r) || {precedence: 0, assoc: 'L'}; while(op.precedence < stack[stack.length-1].precedence || (op.precedence == stack[stack.length-1].precedence && op.assoc == 'L')) { // precedence op is too low, calculate with what we've got on the left, first var tos = stack.pop(); if(!tos.exec) return value; // end reached // do the calculation ("reduce"), producing a new value value = tos.exec(tos.value, value); } // store on stack and continue parsing ("shift") stack.push({op: op.op, precedence: op.precedence, assoc: op.assoc, exec: op.exec, value: value}); value = parseVal(r); // value on the right } } function parse (string) { // wrapper var r = {string: string, offset: 0}; try { var value = parseExpr(r); if(r.offset < r.string.length){ r.error = 'Syntax error: junk found at offset ' + r.offset; throw 'trailingJunk'; } return value; } catch(e) { alert(r.error + ' (' + e + '):\n' + r.string.substr(0, r.offset) + '<*>' + r.string.substr(r.offset)); return; } } 

Answer 6

如果你能描述你当前正在使用的语法来解析，这将有所帮助。 听起来像问题可能在那里！

编辑：

你不了解语法问题，而且“你手写这个东西”这个事实很可能解释了为什么你遇到了表达式'1 + 11 * 5'的问题（也就是运算符优先级） 。 例如，谷歌搜索“算术表达式的语法”应该会产生一些好的指针。 这样的语法不需要很复杂：

 <Exp> ::= <Exp> + <Term> | <Exp> - <Term> | <Term> <Term> ::= <Term> * <Factor> | <Term> / <Factor> | <Factor> <Factor> ::= x | y | ... | ( <Exp> ) | - <Factor> | <Number> 

会做的伎俩，例如，可以平凡增强照顾一些更复杂的表达式（包括功能，例如，权力，…）。

例如，我建议你看看这个线程。

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

请注意，使用语法并不意味着使用特定的工具（ la Yacc，Bison，…）。 事实上，你当然已经在使用下面的语法：

 <Exp> :: <Leaf> | <Exp> <Op> <Leaf> <Op> :: + | - | * | / <Leaf> :: <Number> | (<Exp>) 

（或类似的东西）而不知道它！

Answer 7

你有没有想过使用Boost Spirit ？ 它允许你用C ++编写像EBNF这样的语法：

 group = '(' >> expression >> ')'; factor = integer | group; term = factor >> *(('*' >> factor) | ('/' >> factor)); expression = term >> *(('+' >> term) | ('-' >> term)); 

Answer 8

有没有你想用的语言？ ANTLR会让你从Java的角度来做这件事。 Adrian Kuhn对如何在Ruby中编写可执行语法做了精彩的写作 ; 实际上，他的例子几乎就是你的算术表达式例子。

Answer 9

这取决于你想要如何“一般”。

如果你希望它真的是一般的，比如像sin（4 + 5）* cos（7 ^ 3）那样能够解析数学函数，你可能需要一个解析树。

其中，我认为在这里贴一个完整的实现是不合适的。 我建议你检查一个臭名昭着的“ 龙书 ”。

但是如果你只是想优先支持 ，那么你可以通过首先将表达式转换为后缀表单，在该表单中可以复制和粘贴的算法可以从谷歌获得，或者我认为你可以用二进制代码树。

当你使用后缀形式的时候，那么从那时起它就是小菜一碟了，因为你已经理解了栈的作用。

Answer 10

我会建议作弊和使用调车场算法 。 这是一个简单的方法来编写一个简单的计算器类型的解析器，并优先考虑。

如果你想正确地标记事物，并有变量等参与，那么我会继续前进，并写一个递归下降解析器在这里别人建议，但是，如果你只是需要一个计算器式解析器，那么这个算法应该是足够的:-)

Answer 11

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

哈罗德写道：

我记得很久以前读过一个算法，它将代数表达式转换成RPN，以便于评估。 每个中缀值或操作员或括号都代表轨道上的一辆铁路车。 一种类型的汽车分开到另一个轨道，另一个继续前进。 我不记得细节（显然！），但总是认为这将是有趣的代码。 当我写6800（不是68000）汇编代码时，这又回来了。

这是“分流院子algorythm”，这是大多数机器解析器使用。 请参阅维基百科上有关解析的文章。 一个简单的方法来编码分流场algorythm是使用两个堆栈。 一个是“推”堆栈，另一个是“减少”或“结果”堆栈。 例：

pstack =（）//空rstack =（）输入：1 + 2 * 3优先级= 10 //最低降低= 0 //不减少

start：token'1'：isnumber，放入pstack（push）token'+'：isoperator set precedence = 2 if precedence <previous_operator_precedence then reduce（）//见下面在pstack（push） ：isnumber，放入pstack（push）标记'*'：isoperator，设置precedence = 1，放入pstack（push）//检查优先级为//上面的标记'3'：isnumber，放入pstack（push）输入，需要减少（目标是空的pstack）reduce（）//完成

为了减少从push栈中弹出元素，并把它们放到结果堆栈中，如果它们的形式为'operator''number'，那么总是在pstack上交换最前面的2个元素：

pstack：'1''+''2'' ''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上加上一个标记，告诉reduce的algorythm在求解paren对的内部时停止减少。 关闭paren会像输入结束一样触发一个缩减，并且还会从pstack中删除打开的paren标记，并恢复“以前的操作”优先级，以便解析可以在关闭paren之后继续。 这可以通过递归或不通过（提示：遇到一个'（'…）时使用一个堆栈来存储先前的优先级。这个的通用版本是使用一个解析器生成器实现分流码algorythm，f.ex.使用yacc或bison或taccle（yacc的tcl类似物）。

彼得

-亚当

Answer 12

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

1）。 Postfix表示法是为了消除显式优先级规范的需要而发明的。 在网上阅读更多，但这是它的要点：中缀表达式（1 + 2）* 3，而人容易读取和处理不是很有效的计算机通过。 什么是？ 简单的规则说：“通过优先缓存重写表达式，然后总是从左到右处理”。 所以中缀（1 + 2）* 3变成后缀12 + 3 *。 POST因为操作符总是放在操作数之后。

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

让我们做后缀（1 + 2）* 3是“12 + 3 *”。 读取第一个数字= 1.将它推入堆栈。 接下来阅读。 数字= 2.推入堆栈。 接下来阅读。 操作员。 哪一个？ +。 哪一种？ 二进制=需要两个操作数。 弹出堆栈两次= argright是2，argleft是1. 1 + 2是3.将3推回堆栈。 从后缀字符串读取下一个。 它是一个数字。 3.Push。 接下来阅读。 操作员。 哪一个？ *。 哪一种？ 二进制=需要两个数字 – >弹出堆栈两次。 首先进入argright，第二次进入argleft。 评估操作 – 3次3是9.按9堆栈。 阅读下一个postfix字符。 它是空的。 输入结束。 Pop stack onec =这就是你的答案。

3）。 Shunting Yard用于将人类（容易）可读的中缀表达转换为后缀表达式（在一些练习之后，人类也容易读取）。 易于手动编码。 见上面的评论和净。

Answer 13

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

 #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("))))\n"); return 0; } 

调用它为：

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

这简直太棒了，非常容易理解。

Answer 14

我已经在我的网站上发布了超紧凑（1类，<10 KiB） Java数学评估器的源代码。 这是一个类型的递归下降解析器，导致接受答案的海报头颅爆炸。

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

Answer 15

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

Answer 16

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

Answer 17

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

Answer 18

使用pyparsing的Python解决方案可以在这里找到。 用各种运算符优先解析中缀表示法是相当普遍的，所以pyparsing也包含了operatorPrecedence表达式构建器。 有了它，你就可以使用“AND”，“OR”，“NOT”来轻松定义布尔表达式。 或者，您可以扩展您的四功能算术使用其他运算符，如！ 为factorial或“％”为模数，或者添加P和C运算符来计算排列和组合。 你可以写一个矩阵符号的中缀解析器，包括处理'-1'或'T'运算符（用于反转和转置）。 4个函数解析器的operatorPrecedence示例（用'！'引出来有趣）在这里 ，一个更全面的解析器和评估器在这里 。

Answer 19

我发布了一个基于Dijkstra的Shunting Yard算法的表达式解析器， 遵循 Apache License 2.0的条款：

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

Answer 20

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

我打算把这个扩展成一个支持任意DSL的语言，但是我只想指出一个不需要定制的解析器来实现运算符的优先级，可以使用一个通用的解析器，它根本不需要表，只是查看每个运算符的优先级。 人们一直在提及定制普拉特解析器或分流码解析器，可以接受非法输入 – 这个不需要定制，（除非有错误）不会接受不好的输入。 从某种意义上讲，它并不是完整的，它是为了测试算法而编写的，它的输入是一种需要预处理的形式，但有些注释说明了这一点。

注意一些常见类型的操作符缺少例如用于索引的操作符类型，即table [index]或调用函数函数（parameter-expression，…）我将添加这些操作符，但将它们都视为后缀运算符中的定界符'['和']'或'（'和'）'之间的内容是用不同的表达式解析器实例解析的。 对不起，已经离开了，但后缀部分是 – 添加其余的可能几乎两倍的代码大小。

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

任意决定的一些细节：

如果低优先级后缀运算符竞争相同的中缀块作为低优先级前缀运算符，则前缀运算符获胜。 这在大多数语言中没有出现，因为大多数语言没有低优先级的后缀运算符。 – （例如：（数据a）（左边1 +）（前面2不是）（数据b）（后面3！）（左边1 +）（数据c））是a + not b！+ c where not前缀运算符和！ 是后缀运算符，两者的优先级均低于+，所以他们希望以不兼容的方式（a + not b！）+ c或a +（not b！+ c）进行分组，所以在这些情况下前缀运算符总是胜出，所以其次是它解析的方式

非关联中缀运算符真的存在，所以你不必假装返回不同类型的运算符比它们合理，但是没有不同的表达式类型。 因此，在这个算法中，非关联运算符拒绝不仅与自己关联，而且与任何具有相同优先级的运算符关联。 这是一个常见的情况，因为<= ==> =等在大多数语言中都不相互关联。

关于不同类型的操作符（左，前缀等）如何断开优先级的问题是不应该出现的问题，因为给不同类型的操作符以相同的优先级是没有意义的。 这种算法在这种情况下做了一些事情，但是我甚至不打算弄清究竟是什么，因为这样的语法首先是一个坏主意。

 #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) 

Answer 21

Here is a simple case recursive solution written in Java. Note it does not handle negative numbers but you can do add that if you want to:

 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; } 

}