具有优先级的方程(表达式)解析器？

小开

It would help if you could describe the grammar you are currently using to parse. Sounds like the problem might lie there!

编辑:

事实上，你不理解语法问题和“你已经手写了这个”很可能解释了为什么你有问题的表达式’1 + 11 * 5’(即，与操作符优先级)。例如，在谷歌上搜索“算术表达式的语法”，应该会得到一些很好的指点。这种语法不必复杂:

<Exp> ::= <Exp> + <Term> |
<Exp> - <Term> |
<Term>


<Term> ::= <Term> * <Factor> |
<Term> / <Factor> |
<Factor>


<Factor> ::= x | y | ... |
( <Exp> ) |
- <Factor> |
<Number>

例如，可以使用这个技巧，并且可以进行微不足道的扩展，以处理一些更复杂的表达式(例如函数，或者幂，...)。

例如，我建议您查看一下这个线程。

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

请注意，使用语法并不意味着使用特定的工具(a la Yacc、 Bison、 ...)。事实上，你肯定已经在使用以下语法:

<Exp>  :: <Leaf> | <Exp> <Op> <Leaf>


<Op>   :: + | - | * | /


<Leaf> :: <Number> | (<Exp>)

(or something of the kind) without knowing it!

小开

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

小开

这取决于你希望它是多么“一般”。

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

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

但是如果你只是想要优先级支持 ，那么你可以首先将表达式转换成后缀形式，在这种形式下，你可以从谷歌中复制粘贴算法，或者我认为你可以用二叉树自己编码。

当你有了后缀形式，那么从那时起就是小菜一碟，因为你已经知道堆栈如何帮助。

小开

最佳答案

来硬的

你需要递归下降解析器。

为了获得优先级，需要递归地思考，例如，使用示例字符串,

1+11*5

要手动完成这项工作，您必须读取 1，然后看到加号，并从 11开始启动一个全新的递归解析“会话”... ... 并确保将 11 * 5解析为它自己的因子，从而生成一个包含 1 + (11 * 5)的解析树。

甚至试图解释这一切都让人觉得很痛苦，特别是 C 的无能为力。看，在解析了11之后，如果 * 实际上是一个 + ，你将不得不放弃尝试制造一个术语，而是解析 11本身作为一个因子。我的头已经快爆炸了。这是可能的递归体面的策略，但有一个更好的方法..。

简单(正确)的方法

如果你使用像 Bison 这样的 GPL 工具，你可能不需要担心许可问题，因为 Bison 生成的 C 代码不在 GPL 范围内(IANAL，但是我很确定 GPL 工具不会强迫生成的代码/二进制文件使用 GPL; 例如，苹果编译的代码就像，Aperture 和 GCC，他们不需要 GPL 说的代码就可以出售)。

Download Bison (or something equivalent, ANTLR, etc.).

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

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

看一下生成的代码，就会发现这并不像听起来那么简单。此外，使用 Bison 这样的工具的好处是: 1)你可以学到一些东西(特别是如果你读了 Dragon 的书并学习了语法) ; 2)你可以避免国家卫生研究院试图重新发明轮子。通过一个真正的解析器生成器工具，您实际上有望在以后进行扩展，向其他人展示解析器是解析工具的领域。

Update:

这里的人们提出了许多合理的建议。对于跳过解析工具，或者仅仅使用 Shunting Yard 算法，或者手卷递归的像样的解析器，我唯一的警告是，小小的玩具语言 ^{译自: 美国《科学》杂志网站(http://docs.garagegames.com/tgea/officer/content/document/Scripting% 20Reference/Guide/TorqueScript.html)}有朝一日可能会变成带有函数(sin，cos，log)、变量、条件和 for 循环的大型实际语言。

对于一个小型、简单的解释器来说，Flex/Bison 可能有些夸张，但是一个一次性的解析器 + 计算器可能会在需要进行更改或需要添加特性时造成麻烦。你的情况会有所不同，你需要使用你的判断，只是不要为你的罪恶惩罚别人 ^[2]和建立一个不足够的工具。

我最喜欢的解析工具

世界上最好的工具是秒差距库(用于递归体面的解析器) ，它与编程语言 Haskell 一起提供。它看起来很像 BNF，或者像一些解析的专门工具或领域特定语言(示例代码[3]) ，但实际上它只是哈斯克尔的一个常规库，这意味着它和其他 Haskell 代码在相同的构建步骤中编译，你可以编写任意的 Haskell 代码并在解析器中调用它，你还可以混合和匹配其他库 都用同样的密码。(顺便说一下，将这样的解析语言嵌入到 Haskell 以外的语言中会导致大量的语法错误。我在 C # 中做了这个，它工作得很好，但是它不是那么漂亮和简洁。)

备注:

理查德·斯托曼说，为什么你不应该使用 Tcl

The principal lesson of Emacs is that 用于扩展的语言不应该仅仅是一种“扩展语言” should be a real programming language, 为编写和维护而设计的 substantial programs. Because people 会想这么做的！

[2]是的，使用那种“语言”给我留下了永远的伤疤。

还要注意的是，当我提交这个条目时，预览是正确的，但是 SO 不足以解析第一段中的关闭锚标记，证明解析器是不容小觑的，因为如果您使用正则表达式和一次性修改 你可能会得到一些细微的错误。

[3] Snippet of a Haskell parser using Parsec: a four function calculator extended with exponents, parentheses, whitespace for multiplication, and constants (like pi and 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

小开

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

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

小开

The 调车场算法调车场算法 is the right tool for this. Wikipedia is really confusing about this, but basically the algorithm works like this:

比方说，你想计算1 + 2 * 3 + 4。直观地说，你“知道”你必须先做2 * 3，但是你是如何得到这个结果的呢？关键是要认识到，当您从左到右扫描字符串时，当操作符 接下来的优先级较低(或等于)时，您将计算操作符。在这个示例的上下文中，您需要这样做:

看: 1 + 2，什么都别做。
现在看1 + 2 * 3，仍然什么都不做。
现在看1 + 2 * 3 + 4，现在你知道2 * 3必须被求值，因为下一个运算符的优先级较低。

如何实现这一点？

您需要有两个堆栈，一个用于编号，另一个用于运算符。你总是把数字放到堆栈上。你比较每个新操作符和堆栈顶部的操作符，如果堆栈顶部的操作符具有更高的优先级，你将它从操作符堆栈中弹出，将操作数从数字堆栈中弹出，应用操作符并将结果推送到数字堆栈中。现在重复与堆栈顶部运算符的比较。

Coming back to the example, it works like this:

N = [ ] 行动中心 = []

阅读1。 N = [1] ，操作 = []
Read +. N = [1], Ops = [+]
Read 2. N = [1 2], Ops = [+]
读 *. N = [12] ，Ops = [ + * ]
读3. N = [123] ，Ops = [ + * ]
读取 + . N = [123] ，运算符 = [ + * ]
- 弹出3、2并执行2*3，然后将结果推送到 N. N = [16] ，Ops = [ + ]
- +是左关联的，所以您还需要弹出1,6并执行 + 。N = [7] ，行动中心 = []。
- Finally push the [+] onto the operator stack. N = [7], Ops = [+].
读4. N = [7] . Ops = [ + ]。
没有输入了，所以现在需要清空堆栈。你会得到结果11。

这并不是很困难，不是吗? 而且它不会调用任何语法或解析器生成器。

小开

很久以前，我创建了自己的解析算法，这在任何有关解析的书籍(比如《龙书》)中都找不到。看看指向调车场算法的指针，我确实看到了相似之处。

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

它非常适合用数字进行直接计算，但是如果必须的话，可以使用它来生成解析树。

Update Because more people can read (or run) Javascript, I've reimplemented my parser in Javascript, after the code has been reorganized. The whole parser is under 5k of Javascript code (about 100 lines for the parser, 15 lines for a wrapper function) including error reporting, and comments.

你可以在 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;
}
}

小开

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

小开

有一篇很好的文章给你介绍了如何将简单的递归下降解析器与操作符优先级解析相结合。如果您最近一直在编写解析器，那么阅读它应该是非常有趣和有益的。

小开

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

小开

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

小开

我在字幕表上找到了这个关于调车场算法的:

哈罗德写道:

我记得很久以前读到过一个算法代数表达式到 RPN，以便于计算。每个中缀值或运营商或括号表示的是一个铁路车厢在一个第一首那种车分开到另一条轨道上，另一条继续直行我不记得细节了(当然!) ，但我总是这样想这是回到我写6800的时候(不是 68000)汇编代码。

这就是“调车场算法” 它是大多数机器解析器参见关于解析的文章一种简单的编码方法调车场算法是用两个堆栈。一个是“推”堆栈和另一个是“减少”或“结果” 例如:

Pstack = ()//空 rstack = () 输入: 1 + 2 * 3优先级 = 10//最低不要减少

标记’1’: isnumber，put in Pstack (push)令牌’+’: isOperator 如果优先级 < ，则设置优先级 = 2 那么, Reduce ()//见下文，输入“ +” Pstack (push)标记’2’: isnumber, Put in pstack (push) token’*’: IsOperator，设置优先级 = 1，放入 Pstack (push)//检查优先级作为 //上面的标记’3’: isnumber，put in Pstack (push)输入结束，需要 Reduce (目标是空 pstack) reduce () 完成

来减少，从推送中弹出元素堆叠并将它们放入结果中堆栈，总是交换上面的2个项目如果它们的形式为 “接线员”“号码”:

Pstack: “1”+ “2”< em > “3”rstack: () ... pstack: () rstack: '3' '2' '' '1' '+'

如果表达式是:

1 * 2 + 3

那么还原触发器就会正在读取令牌’+’ 优先级低于 '*' already pushed, so it would have 完成:

Pstack: “1”< em > “2”rstack: () ..。 Pstack: () rstack:’1’’2’’

然后按“ +”然后按“3” then finally reduced:

Pstack:’+’3’rstack:’1’’2’< em >’ ... pstack: () rstack:’1’2’’3’ '+'

简而言之，推送号码, 当按操作员检查 precedence of the previous operator. 如果它高于操作员的就是现在推，先推减少，然后推动电流要处理括号，只需保存 “以前”的优先级操作符，并在 pstack 上添加一个标记它告诉 reduce 算法 stop reducing when solving the inside of a paren pair. The closing paren 触发一个减少作为做结束输入，并删除打开的 paren mark from the pstack, and 恢复“以前的操作” 优先级，以便继续解析在它离开的右括号之后这可以通过递归来完成或没有(提示: 使用堆栈来存储以前的优先次序遇到一个’(’...) 本文的通用版本是使用编译器编译程式实施调车场算法，使用野牛或接触器 Yacc).

彼得

亚当

小开

I have posted source for an ultra compact (1 class, < 10 KiB) Java 数学计算器 on my web site. This is a recursive descent parser of the type that caused the cranial explosion for the poster of the accepted answer.

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

小开

优先级解析的另一个资源是 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))))

它的简洁令人敬畏，也很容易理解。

小开

你考虑过使用振奋精神吗? 它允许你用 C + + 编写类似 EBNF 的语法，如下所示:

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

小开

可以找到使用 pyparsing 的 Python 解决方案给你。使用具有优先级的各种操作符解析中缀表示法是相当常见的，因此解析还包括 infixNotation(以前是 operatorPrecedence)表达式构建器。有了它，你可以很容易地定义布尔表达式使用“ AND”，“ OR”，“ NOT”，例如。或者您可以将四个函数的算法扩展为使用其他运算符，例如！对阶乘，或’%’对模，或添加 P 和 C 运算符来计算排列和组合。您可以为矩阵表示法编写一个中缀解析器，其中包括处理“-1”或“ T”运算符(用于反转和转置)。具有4个函数的解析器(使用“ !”是给你，一个功能更全面的解析器和求值器是 here。

小开

Http://www.engr.mun.ca/~theo/misc/exp_parsing.htm

很好地解释了不同的方法:

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

Written in simple language and pseudo-code.

我喜欢“优先级攀升”。

小开

我发布了一个基于 Dijkstra's Shunting Yard算法的表达式解析器，根据 Apache 许可证2.0的条款:

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

小开

当你提出你的问题时，就不需要递归了。答案是三件事: 逆波兰表示法加上分车场算法加上后缀表达式评估:

1).逆波兰表示法是为了消除显式优先级规范的需要而发明的。在网上阅读更多，但这里是它的要点: 中缀表达式(1 + 2) * 3，虽然容易为人类读取和处理不是非常有效的计算通过机器。什么？一个简单的规则: “通过优先缓存重写表达式，然后始终从左到右处理它”。所以 infix (1 + 2) * 3变成了后缀12 + 3 * 。POST，因为操作符总是放在操作数之后。

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

让我们做(1 + 2) * 3，后缀是“12 + 3 *”。读第一个数字 = 1。推到栈上。接下来读。数字 = 2。推到栈上。接下来读。接线员。哪一个？+.什么样的？Binary = 需要两个操作数。弹出堆栈 two = argright 为2，argleft 为1。1 + 2等于3。把3推回栈上。接下来从后缀字符串读取。是个数字。3.用力。接下来读。接线员。哪一个？*.什么样的？Binary = 需要两个数字-> 弹出堆栈两次。第一次进入 argright，第二次进入 argleft。评估操作3乘以3等于9。按9。读下一个后缀字符。无效。输入结束。这就是你的答案。

3).分流场是用来转换人类(容易)可读的中缀表达到后缀表达(也人类容易阅读后，一些实践)。易于手动编码。请看上面的评论和网页。

小开

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

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

注意一些常见类型的运算符缺失，例如用于为 ie table [ index ]建立索引或调用函数函数(参数表达式，...)的运算符类型我将添加这两个操作符，但是将它们都看作后缀操作符，其中分隔符“[’和’]”或“(’和’)”之间的内容将使用表达式解析器的不同实例进行解析。很抱歉遗漏了这一点，但是后缀部分已经加入——添加其余部分可能会使代码的大小几乎增加一倍。

Since the parser is just 100 lines of racket code, perhaps I should just paste it here, I hope this isn't longer than stackoverflow allows.

关于任意决定的一些细节:

如果低优先级后缀运算符与低优先级前缀运算符竞争相同的中缀块，则该前缀运算符获胜。这在大多数语言中不会出现，因为大多数语言没有低优先级的后缀操作符。 - 例如: ((数据 a)(左1 +)(前2不)(数据 b)(后3!)(左1 +)(数据 c)) 是 a + not b! + c，其中 not 是前缀操作符，! 是后缀操作符，两者都有小写因此，他们希望以不兼容的方式进行分组 (a + 不是 b!) + c or as 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 编写的一个简单的 case 递归解决方案。注意，它不处理负数，但是如果你想要的话，你可以添加:

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

_{下一个例子可能有用:} _{Yupana -严格的算术运算;} _{Tinyexpr -算术运算 + C 数学函数 + 用户提供的函数;} _{Mpc -解析器组合器}

Explanation

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

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，否则，在 _{这是我们生产规则中的左选项}后面计算符号，返回 term.value * product.value _{这是正确的选择，在我们的生产规则，即 term "*" product}

小开

实际上有一种不用递归的方法可以一个字符一个字符地遍历整个表达式。这是 O (n)表示时间和空间。即使对于中等大小的表达式，也需要5毫秒的运行时间。

首先，你需要检查一下你的括号是否平衡。我这么做不是为了简单。而且，我觉得这就像个计算器。除非用括号括起表达式，否则计算器不应用优先级。

我使用两个堆栈，一个用于操作数，另一个用于操作符。每当我达到一个空白’(’括号，并减少优先级，每当我达到一个结束’)’括号时，我增加操作的优先级。我甚至修改了代码，用小数加上数字。这是 C # 。

注意: 这对负数这样的有符号数字不起作用。可能这只是一个简单的修正。

  internal double Compute(string sequence)
{
int priority = 0;
int sequenceCount = sequence.Length;
for (int i = 0; i < sequenceCount; i++) {
char s = sequence[i];
if (Char.IsDigit(s)) {
double value = ParseNextNumber(sequence, i);
numberStack.Push(value);
i = i + value.ToString().Length - 1;
} else if (s == '+' || s == '-' || s == '*' || s == '/')  {
Operator op = ParseNextOperator(sequence, i, priority);
CollapseTop(op, numberStack, operatorStack);
operatorStack.Push(op);
} if (s == '(') { priority++; ; continue; }
else if (s == ')') { priority--; continue; }
}
if (priority != 0) { throw new ApplicationException("Parens not balanced"); }
CollapseTop(new Operator(' ', 0), numberStack, operatorStack);
if (numberStack.Count == 1 && operatorStack.Count == 0) {
return numberStack.Pop();
}
return 0;
}

为了验证这一点:

Calculator c = new Calculator();
double value = c.Compute("89.8+((9*3)+8)+(9*2)+1");
Console.WriteLine(string.Format("The sum of the expression is: {0}", (float)value));
//prints out The sum of the expression is: 143.8

小开

纯 javascript，不需要依赖

I very like Bart 的回答.

并且我做了一些修改以便更容易地阅读它，同时还增加了一些支持功能(并且很容易扩展)

function Parse(str) {
try {
return parseExpr(str.replaceAll(" ", "")) // Implement? See full code.
} catch (e) {
alert(e.message)
}
}


Parse("123.45+3*22*4")

它可以支持如下所示

const testArray = [
// 👇 Basic Test
["(3+5)*4", ""],
["123.45+3*22*4", ""],
["8%2", ""],
["8%3", ""],
["7/3", ""],
["2*pi*e", 2 * Math.atan2(0, -1) * Math.exp(1)],
["2**3", ""],


// 👇 unary Test
["3+(-5)", ""],
["3+(+5)", ""],


// 👇 Function Test
["pow{2,3}*2", 16],
["4*sqrt{16}", 16],
["round{3.4}", 3],
["round{3.5}", 4],
["((1+e)*3/round{3.5})%2", ((1 + Math.exp(1)) * 3 / Math.round(3.5)) % 2],
["round{3.5}+pow{2,3}", Math.round(3.5)+Math.pow(2,3)],
]

全密码

// 👇 Main
(() => {
window.onload = () => {
const nativeConsoleLogFunc = window.console.error
window.console.error = (...data) => { // Override native function, just for test.
const range = document.createRange()
const frag = range.createContextualFragment(`<div>${data}</div>`)
document.querySelector("body").append(frag)
nativeConsoleLogFunc(...data)
}


// Add Enter event
document.querySelector(`input`).onkeyup = (keyboardEvent) => {
if (keyboardEvent.key === "Enter") {
const result = Parse(document.getElementById('expr').value)
if (result !== undefined) {
alert(result)
}
}
}


const testArray = [
// 👇 Basic Test
["(3+5)*4", ""],
["123.45+3*22*4", ""],
["8%2", ""],
["8%3", ""],
["7/3", ""],
["2*pi*e", 2 * Math.atan2(0, -1) * Math.exp(1)],
["2**3", ""],


// 👇 unary
["3+(-5)", ""],
["3+(+5)", ""],


// 👇 Function Test
["pow{2,3}*2", 16],
["4*sqrt{16}", 16],
["round{3.4}", 3],
["round{3.5}", 4],
["((1+e)*3/round{3.5})%2", ((1 + Math.exp(1)) * 3 / Math.round(3.5)) % 2],
["round{3.5}+pow{2,3}", Math.round(3.5) + Math.pow(2, 3)],


// 👇 error test
["21+", ValueMissingError],
["21+*", ParseError],
["(1+2", ParseError], // miss ")"
["round(3.12)", MissingParaError], // should be round{3.12}
["help", UnknownVarError],
]


for (let [testString, expected] of testArray) {
if (expected === "") {
expected = eval(testString) // Why don't you use eval instead of writing the function yourself? Because the browser may disable eval due to policy considerations. [CSP](https://content-security-policy.com/)
}
const actual = Parse(testString, false)


if (actual !== expected) {
if (actual instanceof Error && actual instanceof expected) {
continue
}
console.error(`${testString} = ${actual}, value <code>${expected}</code> expected`)
}
}
}
})()


// 👇 Script
class UnknownVarError extends Error {
}


class ValueMissingError extends Error {
}


class ParseError extends Error {
}


class MissingParaError extends Error {
}


/**
* @description Operator
* @param {string} sign "+", "-", "*", "/", ...
* @param {number} precedence
* @param {"L"|"R"} assoc associativity  left or right
* @param {function} exec
* */
function Op(sign, precedence, assoc, exec = undefined) {
this.sign = sign
this.precedence = precedence
this.assoc = assoc
this.exec = exec
}


const OpArray = [
new Op("+", 10, "L", (l, r) => l + r),
new Op("-", 10, "L", (l, r) => l - r),
new Op("*", 20, "L", (l, r) => l * r),
new Op("/", 20, "L", (l, r) => l / r),
new Op("%", 20, "L", (l, r) => l % r),
new Op("**", 30, "R", (l, r) => Math.pow(l, r))
]


const VarTable = {
e: Math.exp(1),
pi: Math.atan2(0, -1), // https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/atan2
pow: (x, y) => Math.pow(x, y),
sqrt: (x) => Math.sqrt(x),
round: (x) => Math.round(x),
}


/**
* @param {Op} op
* @param {Number} value
* */
function Item(op, value = undefined) {
this.op = op
this.value = value
}


class Stack extends Array {
constructor(...items) {
super(...items)
this.push(new Item(new Op("", 0, "L")))
}


GetLastItem() {
return this[this.length - 1] // fast then pop // https://stackoverflow.com/a/61839489/9935654
}
}


function Cursor(str, pos) {
this.str = str
this.pos = pos
this.MoveRight = (step = 1) => {
this.pos += step
}
this.PeekRightChar = (step = 1) => {
return this.str.substring(this.pos, this.pos + step)
}


/**
* @return {Op}
* */
this.MoveToNextOp = () => {
const opArray = OpArray.sort((a, b) => b.precedence - a.precedence)
for (const op of opArray) {
const sign = this.PeekRightChar(op.sign.length)
if (op.sign === sign) {
this.MoveRight(op.sign.length)
return op
}
}
return null
}
}


/**
* @param {Cursor} cursor
* */
function parseVal(cursor) {
let startOffset = cursor.pos


const regex = /^(?<OpOrVar>[^\d.])?(?<Num>[\d.]*)/g
const m = regex.exec(cursor.str.substr(startOffset))
if (m) {
const {groups: {OpOrVar, Num}} = m
if (OpOrVar === undefined && Num) {
cursor.pos = startOffset + Num.length


if (cursor.pos > startOffset) {
return parseFloat(cursor.str.substring(startOffset, startOffset + cursor.pos - startOffset)) // do not use string.substr() // It will be removed in the future. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Deprecated_and_obsolete_features#string_methods
}
}


if ("+-(".indexOf(OpOrVar) !== -1) {
cursor.pos++
switch (OpOrVar) {
case "+": // unary plus, for example: (+5)
return parseVal(cursor)
case "-":
return -(parseVal(cursor))
case "(":
const value = parseExpr(cursor)
if (cursor.PeekRightChar() === ")") {
cursor.MoveRight()
return value
}
throw new ParseError("Parsing error: ')' expected")
}
}
}




// 👇 below is for Variable or Function
const match = cursor.str.substring(cursor.pos).match(/^[a-z_][a-z0-9_]*/i) // https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/match


if (match) {
// 👇 Variable
const varName = match[0]
cursor.MoveRight(varName.length)
const bracket = cursor.PeekRightChar(1)
if (bracket !== "{") {
if (varName in VarTable) {
const val = VarTable[varName]
if (typeof val === "function") {
throw new MissingParaError(`${varName} is a function, it needs big curly brackets`)
}
return val
}
}


// 👇 is function
const regex = /{(?<Para>[^{]*)}/gm
const m = regex.exec(cursor.str.substring(cursor.pos))
if (m && m.groups.Para !== undefined) {
const paraString = m.groups.Para
const para = paraString.split(',')
cursor.MoveRight(paraString.length + 2) // 2 = { + }
return VarTable[varName](...para)
}
throw new UnknownVarError(`unknown variable ${varName}`)
}


// 👇 Handle Error
if (cursor.str.length === cursor.pos) { // example: 1+2+
throw new ValueMissingError(`Parsing error at end of string: value expected.`)
} else { // example: 1+2+*
throw new ParseError("Parsing error: unrecognized value")
}
}


/**
* @param {string|Cursor} expr
* */
function parseExpr(expr) {
const stack = new Stack()
const cursor = (expr instanceof Cursor) ? expr : new Cursor(expr, 0)
while (1) {
let rightValue = parseVal(cursor)
const op = cursor.MoveToNextOp() ?? new Op("", 0, "L")


while (
op.precedence < stack.GetLastItem().op.precedence ||
(op.precedence === stack.GetLastItem().op.precedence && op.assoc === 'L')) {
const lastItem = stack.pop()
if (!lastItem.op.exec) { // end reached
return rightValue
}
rightValue = lastItem.op.exec(lastItem.value, rightValue)
}


stack.push(new Item(op, rightValue))
}
}


function Parse(str, alertError = true) {
try {
return parseExpr(str.replaceAll(" ", ""))
} catch (e) {
if (alertError) {
alert(e.message)
return undefined
}
return e
}
}

<input type="text" id="expr" name="expr" placeholder="123.45+3*22*4">
<button onclick="const x = Parse(document.getElementById('expr').value); if(x != null) alert(x);">
Calculate!
</button>