具有优先级的方程（表达式）解析器？
https://stackoverflow.com/questions/28256
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我使用简单的堆栈算法开发了一个方程解析器，该算法将处理二元（+、-、|、&、*、/等）运算符、一元（！）运算符和括号。
然而，使用这种方法，让我的所有内容都具有相同的优先级 - 无论运算符如何，它都会从左到右计算，尽管可以使用括号强制执行优先级。
所以现在“1+11*5”返回 60，而不是人们预期的 56。
虽然这适合当前的项目，但我希望有一个可用于以后项目的通用例程。
为了清楚起见进行了编辑：
优先解析方程的好算法是什么？
我对易于实现的东西感兴趣，并且了解我可以自己编写代码以避免可用代码的许可问题。
语法：
我不明白语法问题 - 这是我手写的。它很简单，我认为不需要 YACC 或 Bison。我只需要使用“2+3 * (42/13)”等方程计算字符串。
语言：
我正在用 C 语言执行此操作，但我对算法感兴趣，而不是特定于语言的解决方案。C 的级别足够低，因此在需要时可以很容易地转换为另一种语言。
代码示例
我发布了 简单表达式解析器的测试代码 我上面说的是。项目需求发生了变化，因此我不需要优化代码的性能或空间，因为它没有合并到项目中。它采用原始的详细形式，应该很容易理解。如果我在运算符优先级方面进一步处理它，我可能会选择 宏黑客 因为它在简单性上与程序的其余部分相匹配。不过，如果我在实际项目中使用它，我会选择更紧凑/更快的解析器。
相关问题
-亚当
解决方案
艰难的路
你想要一个 递归下降解析器.
为了获得优先权，您需要递归地思考，例如，使用示例字符串，
1+11*5
要手动执行此操作，您必须阅读 1, ，然后看到加号并开始一个全新的递归解析“会话”，从 11...并确保解析 11 * 5 进入它自己的因子，产生一个解析树 1 + (11 * 5).
即使试图解释，这一切都让人感到如此痛苦，尤其是在 C 增加了无力感的情况下。看，解析 11 后，如果 * 实际上是 +，那么您将不得不放弃创建术语的尝试，而是解析 11 本身作为一个因素。我的头已经爆炸了。使用递归体面策略是可能的，但有更好的方法......
简单（正确）的方法
如果您使用像 Bison 这样的 GPL 工具，您可能不需要担心许可问题，因为 bison 生成的 C 代码不受 GPL 覆盖（IANAL，但我很确定 GPL 工具不会强制使用 GPL）生成的代码/二进制文件；例如，Apple 使用 GCC 编译 Aperture 之类的代码，并且他们无需 GPL 即可出售该代码）。
下载野牛 （或类似的东西，ANTLR等）。
通常有一些示例代码，您可以在其上运行 bison 并获得所需的 C 代码来演示这四个函数计算器：
http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html
查看生成的代码，您会发现这并不像听起来那么容易。另外，使用 Bison 这样的工具的优点是 1）你可以学到一些东西（特别是如果你阅读 Dragon 书并学习语法），2）你可以避免 NIH 试图重新发明轮子。使用真正的解析器生成器工具，您实际上希望以后能够扩大规模，向其他人展示您知道解析器是解析工具的领域。
更新：
这里的人们提出了很多中肯的建议。我对跳过解析工具或仅使用 Shunting Yard 算法或手卷递归体面解析器的唯一警告是小玩具语言1 也许有一天会变成具有函数（sin、cos、log）、变量、条件和 for 循环的大型实际语言。
对于一个小型、简单的解释器来说，Flex/Bison 可能有点过分了，但是当需要进行更改或需要添加功能时，一次性的解析器+评估器可能会导致麻烦。您的情况会有所不同，您需要做出判断；只是不 为你的罪孽惩罚别人 [2] 并构建一个不够充分的工具。
我最喜欢的解析工具
世界上最好的工作工具是 秒差距 编程语言 Haskell 附带的库（用于递归体面解析器）。它看起来很像 BNF, ，或者像一些用于解析的专用工具或领域特定语言（示例代码 [3]），但它实际上只是 Haskell 中的常规库，这意味着它在与 Haskell 代码的其余部分相同的构建步骤中进行编译，并且您可以编写任意 Haskell 代码并在解析器中调用它，并且可以混合和匹配其他库 全部在同一个代码中. 。（顺便说一句，将这样的解析语言嵌入到 Haskell 以外的语言中会导致大量语法错误。我用 C# 做了这个，效果很好，但不是那么漂亮和简洁。）
笔记：
1 理查德·斯托曼说，在 为什么你不应该使用 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 . (\x y -> 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
其他提示
这 调车场算法 是执行此操作的正确工具。维基百科对此确实令人困惑，但基本上该算法的工作原理如下：
假设您要计算 1 + 2 * 3 + 4。直觉上，您“知道”必须先执行 2 * 3，但是如何得到这个结果呢？关键是要认识到，当您从左到右扫描字符串时，当运算符 如下 它具有较低（或等于）的优先级。在示例的上下文中，您想要执行以下操作：
- 看着：1+2，什么都不做。
- 现在看1+2*3，还是什么都不做。
- 现在看看 1 + 2 * 3 + 4，现在您知道必须计算 2 * 3，因为下一个运算符的优先级较低。
你如何实现这一点？
您需要两个堆栈，一个用于数字，另一个用于运算符。您始终将数字压入堆栈。将每个新运算符与堆栈顶部的运算符进行比较，如果堆栈顶部的运算符具有更高的优先级，则将其从运算符堆栈中弹出，将操作数从数字堆栈中弹出，应用运算符并推送结果到号码堆上。现在，您重复与栈顶运算符的比较。
回到这个例子，它的工作原理是这样的：
n = [] ops = [
- 阅读 1。N = [1]，操作 = [ ]
- 读+。N = [1]，操作 = [+]
- 阅读 2。N = [1 2]，操作 = [+]
- 读
*. 。N = [1 2]，操作 = [+ *] - 阅读 3。N = [1 2 3]，操作 = [+ *]
- 读+。N = [1 2 3]，操作 = [+ *]
- 弹出 3、2 并执行 2
*3、将结果推入N。N = [1 6]，操作 = [+] +是左关联的，因此您还想弹出 1、6 并执行 +。N = [7]，操作 = []。- 最后将[+]压入操作符堆栈。N = [7]，操作 = [+]。
- 弹出 3、2 并执行 2
- 阅读 4。N = [7 4]。行动= [+]。
- 您的输入已用完，因此您现在想清空堆栈。此时您将得到结果 11。
在那里，这并不那么困难，不是吗？并且它不会调用任何语法或解析器生成器。
http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
对不同方法的很好的解释：
- 递归下降识别
- 调车场算法
- 经典解决方案
- 优先攀爬
用简单的语言和伪代码编写。
我喜欢“优先攀登”这一点。
有一篇文章不错 这里 关于将简单的递归下降解析器与运算符优先级解析相结合。如果您最近正在编写解析器，那么阅读它应该会非常有趣且具有启发性。
很久以前，我编写了自己的解析算法，但在任何有关解析的书籍（例如《龙之书》）中都找不到该算法。看看调车场算法的指针，我确实看到了相似之处。
大约 2 年前，我发表了一篇关于它的文章，附有 Perl 源代码，位于 http://www.perlmonks.org/?node_id=554516. 。移植到其他语言很容易：我所做的第一个实现是在 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 l-r; } },
'*' : {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;
}
}
如果您能描述当前用于解析的语法，将会有所帮助。听起来问题可能就出在这里！
编辑：
您不理解语法问题并且“您是手写的”这一事实很可能解释了为什么您在使用“1+11*5”形式的表达式（即具有运算符优先级）时遇到问题。例如，在谷歌上搜索“算术表达式语法”应该会产生一些不错的提示。这样的语法不需要很复杂：
<Exp> ::= <Exp> + <Term> |
<Exp> - <Term> |
<Term>
<Term> ::= <Term> * <Factor> |
<Term> / <Factor> |
<Factor>
<Factor> ::= x | y | ... |
( <Exp> ) |
- <Factor> |
<Number>
例如，可以做到这一点，并且可以进行简单的增强以处理一些更复杂的表达式（例如包括函数或幂......）。
我建议你看一下 这 例如，线程。
几乎所有语法/解析的介绍都以算术表达式为例。
请注意，使用语法并不意味着使用特定的工具（阿拉 雅克、野牛……）。事实上，您肯定已经在使用以下语法：
<Exp> :: <Leaf> | <Exp> <Op> <Leaf>
<Op> :: + | - | * | /
<Leaf> :: <Number> | (<Exp>)
（或类似的东西）而不自知！
你有没有想过使用 振奋精神？它允许您用 C++ 编写类似 EBNF 的语法，如下所示：
group = '(' >> expression >> ')';
factor = integer | group;
term = factor >> *(('*' >> factor) | ('/' >> factor));
expression = term >> *(('+' >> term) | ('-' >> term));
当您提出问题时，不需要任何递归。答案是三件事：Postfix表示法加上Shunting Yard算法加上Postfix表达式求值：
1）。后缀表示法 = 发明的目的是消除对明确优先级规范的需要。在网上阅读更多内容，但要点如下：中缀表达式 ( 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.推。接下来阅读。操作员。哪一个？*。哪一种？二进制 = 需要两个数字 -> 弹出堆栈两次。第一次弹出到 argright，第二次弹出到 argleft。评估运算 - 3 乘以 3 等于 9。将 9 压入堆栈。读取下一个后缀字符。它是空的。输入结束。Pop stack onec = 这就是你的答案。
3）。Shunting Yard 用于将人类（易于）可读的中缀表达式转换为后缀表达式（经过一些练习后也易于人类阅读）。易于手动编码。请参阅上面的评论和网络。
我建议作弊并使用 调车场算法. 。这是编写简单计算器类型解析器的一种简单方法，并且考虑了优先级。
如果你想正确地标记事物并拥有变量等。那么我会继续按照其他人的建议编写一个递归下降解析器，但是如果您只需要一个计算器风格的解析器，那么这个算法应该足够了:-)
我在 PIClist 上找到了关于 调车场算法:
哈罗德写道：
我记得很久以前阅读了一种算法，该算法将代数表达式转换为RPN以进行评估。每个Infix值或操作员或括号由轨道上的铁路车代表。一种类型的汽车分开到另一个轨道，另一辆车继续前进。我不记得细节（显然！），但总是认为编码很有趣。当我编写6800（不是68000）装配代码时，这回来了。
这是“分流码算法”，这是大多数机器解析器使用的。请参阅Wikipedia解析的文章。编码分流码算法的一种简单方法是使用两个堆栈。一个是“推”堆栈，另一个是“降低”或“结果”堆栈。例子：
pstack =（）//空rstack =（）输入：1+2*3优先= 10 //最低减少= 0 //不要减少
开始：标记“1”：isnumber，放入pstack（push）代币'+'：等级设置优先级= 2如果优先级<POSTER_OPERATOR_PRECEDENCE，则REDAD（）//请参见下面的PSTACK（push）token'2'：isnumber，放入PSTACK（推）令牌'*'：Isoperator设置优先= 1，放入PSTACK（push）//检查优先级为//上方'3'：isnumber，放入输入的PSTACK（推）末端，需要减少（目标是空PSTACK）redion（）//完成
为了减少推动堆栈中的弹出元素，并将它们放入结果堆栈中，如果它们是“运算符”“数字”的形式：
堆栈：'1''+''2''''3'rstack：（）...堆栈：() 堆栈：'3' '2' '' '1' '+'
如果表达式是：
1*2+3
然后，减少触发器将是对代币'+'的读数，其预定率低于已经推动的“*”，因此它可以做到：
堆栈：‘1’’''2'rstack：() ...堆栈：() 堆栈：'1' '2' ''
然后推动“+”，然后'3'，然后最终减少：
堆栈：'+' '3' rstack：'1' '2' ''...堆栈：() 堆栈：'1' '2' '' '3' '+'
所以简短的版本是：推送数字，推动操作员检查以前的运算符的优先级。如果它高于现在要推的操作员，请首先减少，然后推动当前的操作员。要处理帕伦斯，只需保存“以前”操作员的优先级，然后在PSTACK上放置一个标记，以告诉减少算法在求解帕伦对的内部时停止减少。闭幕式帕伦（Paren）和输入的末端一样，触发了降低，还从PSTACK中删除了开放的Paren标记，并恢复了“以前的操作”优先级，因此在关闭Paren离开的地方后可以继续进行解析。这可以通过递归或没有提示来完成（提示：遇到'（'...）时，请使用堆栈存储先前的优先级。它的广义版本是使用解析器生成器实现的分流码算法，F.Ex.。使用YACC，野牛或TACCLE（YACC的TCL类似物）。
彼得
-亚当
我已经发布了超紧凑型（1 类，< 10 KiB）的源代码 Java 数学计算器 在我的网站上。这是一个递归下降解析器，它导致了已接受答案的发布者的颅骨爆炸。
它支持完整的优先级、括号、命名变量和单参数函数。
我发布了一个基于的表达式解析器 迪克斯特拉调车场 算法，根据条款 阿帕奇许可证 2.0:
优先级解析的另一个资源是 运算符优先级解析器 维基百科上的条目。涵盖了 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))))
这非常简单，而且非常容易理解。
我已经实现了 递归下降解析器 在Java中 MathEclipse 解析器 项目。它也可以用作 谷歌网络工具包 模块
我目前正在撰写一系列文章，构建正则表达式解析器作为设计模式和可读编程的学习工具。你可以看一下 可读代码. 。文章清晰地介绍了调车场算法的使用。
我用 F# 编写了一个表达式解析器 在这里写了关于它的博客. 。它使用调车场算法，但我没有将中缀转换为 RPN，而是添加了第二个堆栈来累积计算结果。它正确处理运算符优先级，但不支持一元运算符。不过，我写这篇文章是为了学习 F#，而不是学习表达式解析。
可以找到使用pyparsing的Python解决方案 这里. 。使用具有优先级的各种运算符解析中缀表示法相当常见，因此 pyparsing 还包括 infixNotation （以前 operatorPrecedence) 表达式生成器。使用它，您可以使用“AND”、“OR”、“NOT”等轻松定义布尔表达式。或者您可以扩展您的四函数算术以使用其他运算符，例如 !对于阶乘，或“%”对于模数，或者添加 P 和 C 运算符来计算排列和组合。您可以为矩阵表示法编写一个中缀解析器，其中包括处理“-1”或“T”运算符（用于求逆和转置）。4 函数解析器的operatorPrecedence 示例（为了好玩而添加了“！”）是 这里 功能更齐全的解析器和评估器是 这里.
我知道这是一个迟到的答案，但我刚刚编写了一个小型解析器，它允许所有运算符（前缀、后缀和中缀左、中缀右和非关联）具有任意优先级。
我将把它扩展为一种支持任意 DSL 的语言，但我只是想指出，不需要自定义解析器来实现运算符优先级，可以使用根本不需要表的通用解析器，并且只需查找每个运算符出现的优先级即可。人们一直在提到可以接受非法输入的自定义 Pratt 解析器或调车场解析器 - 这个不需要定制并且（除非有错误）不会接受错误的输入。从某种意义上说，它并不完整，它是为了测试算法而编写的，其输入的形式需要进行一些预处理，但有一些注释表明了这一点。
注意一些常见的运算符类型，例如，用于索引IE表[索引]或调用函数函数的操作员类型（参数 - 示例，...）分隔符'['和']'或'（''and'）之间发生的事情的操作员与表达式解析器的不同实例进行了解析。很抱歉遗漏了这一点，但后缀部分已包含在内 - 添加其余部分可能几乎会使代码大小增加一倍。
由于解析器只有 100 行球拍代码，也许我应该将其粘贴到此处，我希望这不会比 stackoverflow 允许的长度长。
关于任意决定的一些细节：
如果低优先级后缀运算符与低优先级前缀运算符竞争相同的中缀块，则前缀运算符获胜。这在大多数语言中都不会出现，因为大多数语言没有低优先级后缀运算符。- 例如：（（数据A）（左1 +）（pre 2 not）（数据b）（post 3！）（左1 +）（数据C））是a +b！ +c，其中不是前缀操作员，并且！是后缀运算符，并且两者的优先级都比++++++，因此他们想以不兼容的方式分组（a+b！）+c或A+（不是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)
这是一个用 Java 编写的简单案例递归解决方案。请注意，它不处理负数，但如果您愿意，您可以添加它：
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 语言编码为递归下降解析器。
#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\n", expression, eval_expression(expression).value);
return 0;
}
下一个库可能有用： 尤帕纳 - 严格的算术运算； 微小表达式 - 算术运算 + C 数学函数 + 用户提供的函数； 多普勒 - 解析器组合器
解释
让我们捕获代表代数表达式的符号序列。第一个是数字，即重复一次或多次的十进制数字。我们将这种符号称为产生式规则。
number -> [0..9]+
加法运算符及其操作数是另一个规则。它是 number 或任何代表的符号 sum "*" sum 顺序。
sum -> number | sum "+" sum
尝试替代品 number 进入 sum "+" sum 那将是 number "+" number 反过来又可以扩展到 [0..9]+ "+" [0..9]+ 最终可以简化为 1+8 这是正确的加法表达式。
其他替换也将产生正确的表达式： sum "+" sum -> number "+" sum -> number "+" sum "+" sum -> number "+" sum "+" number -> number "+" number "+" number -> 12+3+5
我们可以一点一点地类似于一组生产规则 又名语法 表达所有可能的代数表达式。
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。实现只是将模式识别与评估结合起来，因此紧密地反映了生产规则。
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
