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

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

编辑：

你不理解语法问题，而且“你是手写的”，这很可能解释了为什么你在使用“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>)

（或类似的东西）在不知不觉中！

有没有你想使用的语言？ANTLR 将允许您从 Java 的角度执行此操作。Adrian Kuhn 写了一篇关于如何在 Ruby 中编写可执行语法的优秀文章;事实上，他的例子几乎完全是你的算术表达式例子。

这取决于你希望它有多“通用”。

如果你希望它非常通用，比如能够解析数学函数，比如 sin（4+5）*cos（7^3），你可能需要一个解析树。

其中，我认为不宜在此处粘贴完整的实现。我建议你看看一本臭名昭著的“龙书”。

但是，如果您只是想要优先级支持，那么您可以通过首先将表达式转换为后缀形式来做到这一点，其中您应该可以从 google 获得可以复制和粘贴的算法，或者我认为您可以自己用二叉树对其进行编码。

当你以后缀形式拥有它时，从那时起它就是小菜一碟，因为你已经了解了堆栈是如何提供帮助的。

艰难的道路

您需要一个递归下降解析器。

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

1+11*5

要手动执行此操作，您必须阅读 ，然后查看加号并启动一个全新的递归解析“会话”，以 ...并确保将 解析为它自己的因子，生成一个带有 .11111 * 51 + (11 * 5)

即使试图解释这一切也感觉如此痛苦，尤其是在 C 的无能为力的情况下。看，在解析了 11 之后，如果 * 实际上是一个 +，你将不得不放弃创建项的尝试，而是将它本身解析为一个因子。我的脑袋已经爆炸了。递归体面策略是可能的，但有更好的方法......11

简单（正确）的方法

如果你使用像 Bison 这样的 GPL 工具，你可能不需要担心许可问题，因为 bison 生成的 C 代码不在 GPL 的涵盖范围内（IANAL，但我很确定 GPL 工具不会在生成的代码/二进制文件上强制使用 GPL;例如，Apple 使用 GCC 编译 Aperture 等代码，他们无需 GPL 所述代码即可出售它）。

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

通常有一些示例代码，你可以在上面运行 bison 并获得你想要的 C 代码来演示这个四个函数计算器：

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

查看生成的代码，发现这并不像听起来那么容易。此外，使用像 Bison 这样的工具的好处是 1） 你可以学到一些东西（特别是如果你阅读 Dragon 书并学习语法），2） 你避免了 NIH 试图重新发明轮子。有了真正的解析器-生成器工具，你实际上有希望在以后扩大规模，向其他人展示你所知道的解析器是解析器工具的领域。

更新：

这里的人们提出了许多中肯的建议。我唯一警告不要跳过解析工具或仅使用 Shunting Yard 算法或手动递归体面的解析器，小玩具语言¹ 有朝一日可能会变成具有函数（sin、cos、log）和变量、条件和 for 循环的大型实际语言。

Flex/Bison 对于一个小型、简单的解释器来说可能有点矫枉过正，但是当需要进行更改或需要添加功能时，一次性的解析器+评估器可能会造成麻烦。你的情况会有所不同，你需要运用你的判断力;只是不要因为你的罪而惩罚别人 ^[2] 并建立一个不够合适的工具。

我最喜欢的解析工具

世界上最好的工具是 Parsec 库（用于递归体面的解析器），它带有编程语言 Haskell。它看起来很像 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 . (\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. 看：1+2，什么都不做。
2. 现在看看 1 + 2 * 3，还是什么都不做。
3. 现在看一下 1 + 2 * 3 + 4，现在您知道必须计算 2 * 3，因为下一个运算符的优先级较低。

你如何实现这一点？

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

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

N = [ ] 操作 = [ ]

• 阅读 1.N = [1]， 运算 = [ ]
• 阅读 +。N = [1]，运算 = [+]
• 阅读 2.N = [1 2]，运算 = [+]
• 读。N = [1 2]，运算 = [+ *]*
• 阅读 3.N = [1 2 3]， 运算 = [+ *]
• 阅读 +。N = [1 2 3]， 运算 = [+ *]
  • 弹出 3、2 并执行 23，并将结果推送到 N. N = [1 6]， Ops = [+]*
  • +是左联想的，所以你也想弹出 1、6 并执行 +。N = [7]，运算 = []。
  • 最后，将 [+] 推到算子堆栈上。N = [7]，操作 = [+]。
• 阅读 4.N = [7， 4]。操作 = [+]。
• 您的输入已用完，因此您现在要清空堆栈。在此基础上，您将得到结果 11.

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

很久以前，我编造了自己的解析算法，在任何关于解析的书籍（如《龙之书》）中都找不到。查看指向调车场算法的指针，我确实看到了相似之处。

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

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

更新因为更多的人可以阅读（或运行）Javascript，所以在代码重新组织后，我在 Javascript 中重新实现了我的解析器。整个解析器不到 5k 的 Javascript 代码（解析器大约 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;
    }    
}

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

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

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

我用 F# 编写了一个表达式解析器，并在这里写了一篇关于它的博客。它使用调车场算法，但我没有从 infix 转换为 RPN，而是添加了第二个堆栈来累积计算结果。它可以正确处理运算符优先级，但不支持一元运算符。不过，我写这篇文章是为了学习 F#，而不是为了学习表达式解析。

我在 PIClist 上找到了关于调车场算法的这个：

哈罗德写道：

我记得很久以前读过一种算法，可以转换 RPN 的代数表达式，便于评估。每个中缀值或 运算符或括号由轨道车上的车厢表示 跟踪。一 这种类型的汽车分道扬镳到另一条赛道，另一条继续直行 提前。我不记得细节（显然！），但一直认为 编码会很有趣。这是我写 6800 的时候（不是 68000） 汇编代码。

这就是“调车场算法” 这是大多数机器解析器 用。请参阅有关解析的文章 维基百科。一种简单的编码方法 调车场算法是用两个 栈。一个是“推送”堆栈和 另一个是“减少”或“结果” 叠。例：

pstack = （） // 空 rstack = （） input： 1+2*3 precedence = 10 // 最低 reduce = 0 // 不减少

start： token '1'： isnumber， 放入 pstack （push） token '+'： isoperator 如果优先级<，则设置 precedence=2 然后previous_operator_precedence reduce（） // 见下文，把 '+' 放进去 pstack （push） token '2'： isnumber， 放入 pstack （push） 令牌 '*'： is运算符，设置优先级=1，放入 pstack （push） // 检查优先级 上面的标记 '3'： isnumber， 放入 pstack（push）端输入，需要 reduce（目标是空的pstack） reduce（） 做

为了减少，从推送中弹出元素 堆栈并将它们放入结果中 堆叠，始终将前 2 个项目交换 pstack（如果它们属于以下形式） 'operator' 'number'：

pstack： '1' '+' '2' ''' '3' rstack： （） ...pstack： （） rstack： '3' '2' ''' '1' '+'

如果表达式是：

1*2+3

那么 reduce 触发器将有 是标记“+”的读数 其优先级低于 '*' 已经推送了，所以它会 做：

pstack： '1' '' '2' rstack： （） ... pstack： （） rstack： '1' '2' ''

然后按“+”，然后按“3”和 然后最后减少：

pstack： '+' '3' rstack： '1' '2' '' ...pstack： （） rstack： '1' '2' ''' '3' '+'

所以简短的版本是：推送数字， 当推动操作员检查 前一个运算符的优先级。 如果它高于运营商的 这是现在要推动的，首先 减小，然后推动电流 算子。要处理 parens，只需保存 “上一个”的优先级 运算符，并在 pstack 上做标记 这告诉 reduce algorythm 到 求解内部时停止还原 一对。闭幕式 触发减少，结束也是如此 的输入，并且还删除了 来自 pstack 的 paren 标记，以及 恢复“先前的操作” 优先级，以便解析可以继续 在它离开的关闭 paren 之后 关闭。这可以通过递归来完成 或不带（提示：使用堆栈存储 上一个优先级 遇到“（”...这 这个的广义版本是使用 实现的解析器生成器 调车场算法，F.Ex.用 YACC 或 Bison 或 Taccle（TCL 类似物 yacc）。

彼得

-亚当

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

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

优先级解析的另一个资源是维基百科上的运算符优先级解析器条目。涵盖了 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))))

它的简单性令人敬畏，而且非常容易理解。

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

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

可以在此处找到使用 pyparsing 的 Python 解决方案。使用具有优先级的各种运算符解析中缀表示法是相当普遍的，因此 pyparsing 还包括（以前的）表达式构建器。有了它，您可以轻松地使用“AND”、“OR”、“NOT”等来定义布尔表达式。或者，您可以扩展四函数算术以使用其他运算符，例如 ！对于阶乘，或“%”表示模数，或添加 P 和 C 运算符来计算排列和组合。您可以为矩阵表示法编写一个中缀解析器，其中包括处理“-1”或“T”运算符（用于反转和转置）。这里是 4 函数解析器的 operatorPrecedence 示例（为了好玩而加入 '！），这里是功能更全面的解析器和计算器。infixNotationoperatorPrecedence

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

对不同方法的很好的解释：

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

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

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

根据 Apache 许可证 2.0 的条款，我发布了一个基于 Dijkstra 的分流场算法的表达式解析器：

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

当你提出你的问题时，不需要任何递归。答案是三件事：后缀表示法加上调车场算法加上后缀表达式计算：

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

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

让我们做 （ 1 + 2 ） * 3，后缀是 “12+3*”。读取第一个数字 = 1。将其推到堆栈上。接下来阅读。数字 = 2。将其推到堆栈上。接下来阅读。算子。哪一个？+.何等？Binary = 需要两个操作数。弹出堆栈两次 = argright 为 2，argleft 为 1。1 + 2 是 3。将 3 推回堆栈上。从 postfix 字符串读取下一个。这是一个数字。3.推。接下来阅读。算子。哪一个？*.何等？二进制 = 需要两个数字 -> pop 堆栈两次。第一次进入 argright，第二次进入 argleft。评估操作 - 3 乘以 3 是 9.将 9 推到堆栈上。阅读下一篇文章 char. 它是 null。输入结束。Pop stack onec = 这就是你的答案。

3）. 调车场用于将人类（易于）可读的中缀表达式转换为后缀表达式（经过一些练习后也易于人类阅读）。易于手动编码。请参阅上面的评论和网络。

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

我将针对具有任意 DSL 支持的语言进行扩展，但我只想指出，不需要自定义解析器来获得运算符优先级，可以使用根本不需要表的通用解析器，并且只需在出现时查找每个运算符的优先级。人们一直在提到可以接受非法输入的自定义 Pratt 解析器或调车场解析器 - 这个不需要自定义，并且（除非有错误）不会接受错误的输入。从某种意义上说，它并不完整，它是为了测试算法而编写的，其输入的形式需要一些预处理，但有一些注释清楚地表明了这一点。

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

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

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

如果低优先级后缀运算符与低优先级前缀运算符争用相同的中缀块，则前缀运算符获胜。这在大多数语言中都没有出现，因为大多数语言都没有低优先级的后缀运算符。 - 例如：（（数据 a） （左 1 +） （前 2 不）（数据 b）（后 3 ！）（左 1 +）（数据c）） 是 a+not b！+c 其中 not 是前缀运算符和 ！是后缀运算符，两者都具有较低的 优先级比 + 好，所以他们希望以不兼容的方式分组为 （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;
}

_{下一个库可能有用：yupana - 严格的算术运算; tinyexpr - 算术运算 + C 数学函数 + 用户提供的函数; MPC - 解析器组合器}

解释

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

number -> [0..9]+

加法运算符及其操作数是另一条规则。 它是表示序列的符号或任何符号。numbersum "*" sum

sum -> number | sum "+" sum

尝试代入，这将是反过来可以扩展为最终可以简化为正确的加法表达式。numbersum "+" sumnumber "+" 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+                                                                    

为了控制操作员的优先级，请更改其生产规则相对于其他规则的位置。查看上面的语法，并注意将生产规则放在下面，这将强制评估之前。 实现只是将模式识别与评估相结合，因此密切反映了生产规则。*+productsum

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

实际上，有一种方法可以在不递归的情况下做到这一点，它允许你逐个字符地遍历整个表达式一次。这是时间和空间的 O（n）。即使对于中等大小的表达式，也需要 5 毫秒才能运行。

首先，您需要进行检查以确保您的parens是平衡的。我在这里不是为了简单起见。另外，我表现得好像这是一个计算器。计算器不应用优先级，除非您将表达式包装在 parens 中。

我使用了两个堆栈，一个用于操作数，另一个用于运算符。每当我到达开口'（'paren时，我都会增加操作的优先级，每当我到达关闭'）'paren时，我都会降低优先级。我什至修改了代码以添加带有小数的数字。这是在 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，无需依赖

我非常喜欢巴特的回答。

我做了一些修改以更容易阅读它，并添加了支持一些功能（并轻松扩展）

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>