114

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

然而,使用这种方法,所有东西都具有相同的优先级——不管运算符如何,它都是从左到右评估的,尽管可以使用括号来强制执行优先级。

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

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

为清楚起见进行了编辑:

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

我对一些易于实现和理解的东西感兴趣,我可以自己编写代码以避免可用代码出现许可问题。

语法:

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

语言:

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

代码示例

我发布了上面提到的简单表达式解析器的测试代码。项目需求发生了变化,因此我不需要针对性能或空间优化代码,因为它没有被合并到项目中。它是原始的详细形式,应该很容易理解。如果我在运算符优先级方面对其进行进一步处理,我可能会选择宏 hack,因为它与程序的其余部分相匹配。但是,如果我在实际项目中使用它,我会选择更紧凑/更快的解析器。

相关问题

数学解析器的智能设计?

-亚当

4

24 回答 24

171

调车场算法是解决此问题的正确工具。维基百科对此真的很困惑,但基本上算法是这样工作的:

比如说,你想计算 1 + 2 * 3 + 4。直觉上,你“知道”你必须先做 2 * 3,但是你是怎么得到这个结果的呢?关键是要意识到,当您从左到右扫描字符串时,您将在其后的运算符具有较低(或等于)优先级时评估该运算。在示例的上下文中,这是您想要执行的操作:

  1. 看:1+2,什么都不做。
  2. 现在看 1 + 2 * 3,还是什么都不做。
  3. 现在看 1 + 2 * 3 + 4,现在您知道必须计算 2 * 3 因为下一个运算符的优先级较低。

你如何实现这一点?

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

回到这个例子,它的工作原理是这样的:

N = [ ] 操作 = [ ]

  • 阅读 1。N = [1],Ops = []
  • 阅读+。N = [1],操作 = [+]
  • 阅读 2。N = [1 2],Ops = [+]
  • 阅读*。N = [1 2],操作 = [+ *]
  • 读取 3。N = [1 2 3],操作 = [+ *]
  • 阅读+。N = [1 2 3],操作 = [+ *]
    • 弹出 3、2 并执行 2 *3,并将结果推送到 N。N = [1 6],Ops = [+]
    • +是左关联的,所以你也想弹出 1、6 并执行 +。N = [7],操作 = []。
    • 最后将 [+] 压入运算符堆栈。N = [7],操作 = [+]。
  • 阅读 4。N = [7 4]。操作 = [+]。
  • 你的输入用完了,所以你现在想清空堆栈。你会得到结果11。

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

于 2008-09-06T18:38:43.503 回答
70

艰难的路

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

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

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 所述代码)。

下载 Bison(或类似的东西,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 附带的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 . (\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
于 2008-08-26T22:39:39.693 回答
26

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

对不同方法的很好解释:

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

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

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

于 2010-03-25T16:27:22.177 回答
18

这里有一篇很好的文章,介绍了将简单的递归下降解析器与运算符优先级解析相结合。如果您最近一直在编写解析器,那么阅读它应该非常有趣且具有启发性。

于 2008-10-09T06:06:34.077 回答
17

很久以前,我自己做了一个解析算法,在任何关于解析的书籍(如龙书)中都找不到。查看指向 Shutting Yard 算法的指针,我确实看到了相似之处。

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

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

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

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

// 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;
    }    
}
于 2008-09-22T13:51:48.120 回答
13

如果您可以描述您当前用于解析的语法,这将有所帮助。听起来问题可能出在那儿!

编辑:

您不理解语法问题并且“您是手工编写的”这一事实很可能解释了为什么您在使用“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>)

(或类似的东西)而不自知!

于 2008-08-26T14:59:37.337 回答
8

您是否考虑过使用Boost Spirit?它允许您在 C++ 中编写类似 EBNF 的语法,如下所示:

group       = '(' >> expression >> ')';
factor      = integer | group;
term        = factor >> *(('*' >> factor) | ('/' >> factor));
expression  = term >> *(('+' >> term) | ('-' >> term));
于 2009-04-28T20:36:41.443 回答
5

我建议作弊并使用Shutting Yard Algorithm。这是编写简单的计算器类型解析器的一种简单方法,并考虑了优先级。

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

于 2008-08-28T18:53:58.393 回答
5

优先级解析的另一个资源是 Wikipedia 上的Operator-precedence parser条目。涵盖了 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))))

它的简单性很棒,而且非常容易理解。

于 2009-04-23T19:10:11.443 回答
5

当您提出问题时,根本不需要递归。答案是三件事:后缀表示法加上 Shutting Yard 算法加上后缀表达式评估:

1)。后缀符号 = 发明以消除对显式优先级规范的需要。在网上阅读更多信息,但这里是它的要点:中缀表达式 (1 + 2) * 3 虽然人类易于阅读和处理,但对于通过机器计算不是很有效。什么是?简单的规则说“通过优先缓存重写表达式,然后总是从左到右处理它”。所以中缀 (1 + 2) * 3 变成了后缀 12+3*。POST 因为运算符总是放在操作数之后。

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

让我们做(1 + 2)* 3,后缀是“12+3*”。读取第一个数字 = 1。将其压入堆栈。接下来阅读。Number = 2。将其压入堆栈。接下来阅读。操作员。哪一个?+。哪一种?Binary = 需要两个操作数。两次弹出堆栈 = argright 为 2,argleft 为 1。1 + 2 为 3。将 3 推回堆栈。从后缀字符串中读取下一个。它是一个数字。3.推。接下来阅读。操作员。哪一个?*。哪一种?二进制 = 需要两个数字 -> 两次弹出堆栈。第一次弹出到 argright,第二次弹出到 argleft。评估操作 - 3 次 3 是 9。将 9 推入堆栈。阅读下一个后缀字符。它是空的。输入结束。弹出堆栈 onec = 这就是你的答案。

3)。Shutting Yard 用于将人类(易于)阅读的中缀表达式转换为后缀表达式(经过一些练习后也易于人类阅读)。易于手动编码。请参阅上面的评论和网络。

于 2012-06-09T00:07:27.993 回答
4

有您想使用的语言吗? ANTLR会让你从 Java 的角度来做这件事。Adrian Kuhn 有一篇关于如何用 Ruby 编写可执行语法的优秀文章;事实上,他的例子几乎就是你的算术表达式例子。

于 2008-08-26T15:04:04.033 回答
4

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

如果您希望它非常通用,例如能够解析数学函数以及 sin(4+5)*cos(7^3) ,您可能需要一个解析树。

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

但是,如果您只是想要优先支持,那么您可以通过首先将表达式转换为后缀形式来实现,在这种形式中,您可以从google获得可以复制和粘贴的算法,或者我认为您可以使用二进制文件自己编写代码树。

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

于 2008-08-26T15:06:22.263 回答
4

我在 PIClist 上找到了关于 Shutting Yard 算法的内容:

哈罗德写道:

我记得很久以前读过一种将代数表达式转换为 RPN 以便于评估的算法。每个中缀值或运算符或括号都由轨道上的火车车厢表示。一种类型的汽车分裂到另一条轨道上,另一种则继续直行。我不记得细节(显然!),但一直认为编码会很有趣。这是我写 6800(不是 68000)汇编代码的时候。

这是“调车场算法”,也是大多数机器解析器使用的。请参阅 Wikipedia 中有关解析的文章。编码调车场算法的一种简单方法是使用两个堆栈。一个是“推”堆栈,另一个是“减少”或“结果”堆栈。例子:

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

start: token '1': isnumber, put in pstack (push) token '+': isoperator set priority=2 if priority < previous_operator_precedence then reduce() // 见下文将'+' in pstack (push) token '2' : isnumber, put in pstack (push) token '*': isoperator, set priority=1, put in pstack (push) // 检查优先级 // 上面的 token '3': isnumber, put in pstack (push) end of输入,需要减少(目标是空的pstack)reduce()//完成

为了减少,从推送堆栈中弹出元素并将它们放入结果堆栈,如果它们的形式为'operator''number',则始终交换 pstack 上的顶部 2 项:

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' '+'

所以简短的版本是:推送数字,在推送运算符时检查前一个运算符的优先级。如果高于现在要推的算子,先reduce,再推当前算子。要处理括号,只需保存“上一个”运算符的优先级,并在 pstack 上放置一个标记,告诉 reduce 算法在解决括号对内部时停止归约。关闭括号会像输入的结尾一样触发缩减,并且还会从 pstack 中删除打开的括号标记,并恢复“先前操作”的优先级,以便解析可以在关闭括号之后继续进行。这可以通过递归或不使用递归来完成(提示:遇到'(' ...)时使用堆栈来存储先前的优先级。这个的通用版本是使用一个解析器生成器实现了调车场算法,f.ex。使用 yacc 或 bison 或 taccle(yacc 的 tcl 类似物)。

彼得

-亚当

于 2008-12-09T20:35:26.153 回答
4

我已经在我的网站上发布了一个超紧凑(1 类,< 10 KiB)Java 数学评估器的源代码。这是一个递归下降解析器,它导致了已接受答案的发布者的颅骨爆炸。

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

于 2008-12-17T19:34:12.187 回答
3

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

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

于 2011-07-23T17:16:40.177 回答
2

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

于 2008-10-03T13:23:45.133 回答
2

我目前正在撰写一系列文章,构建正则表达式解析器作为设计模式和可读编程的学习工具。你可以看看readablecode。这篇文章提出了一个清晰的使用调车码算法。

于 2008-10-09T06:12:02.130 回答
2

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

于 2008-11-05T22:30:17.937 回答
2

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

于 2009-09-04T08:02:45.863 回答
1

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

我将把它扩展为一种支持任意 DSL 的语言,但我只想指出,不需要为运算符优先级定制解析器,可以使用根本不需要表的通用解析器,并且只是查找每个运算符出现的优先级。人们一直在提到可以接受非法输入的自定义 Pratt 解析器或调车场解析器 - 这个不需要定制并且(除非存在错误)不会接受错误输入。它在某种意义上并不完整,它是为了测试算法而编写的,它的输入是需要一些预处理的形式,但有一些评论可以说明这一点。

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

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

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

如果低优先级后缀运算符与低优先级前缀运算符竞争相同的中缀块,则前缀运算符获胜。这在大多数语言中都不会出现,因为大多数语言没有低优先级后缀运算符。- 例如: ((data a) (left 1 +) (pre 2 not)(data b)(post 3 !) (left 1 +) (data c)) is a+not b!+c where not is a前缀运算符和!是后缀运算符,并且两者的优先级都低于 +,因此他们希望以不兼容的方式分组为 (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)
于 2014-03-10T10:17:39.787 回答
1

这是一个用 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;
}

}

于 2017-10-13T04:54:46.730 回答
1

算法可以很容易地用 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]+

加法运算符及其操作数是另一条规则。它是代表序列的任何一个number或任何符号。sum "*" 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+                                                                    

为了控制操作员的优先级,改变它的生产规则相对于其他人的位置。查看上面的语法并注意生产规则 for*放在下面+this 将强制product评估 before 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

于 2018-01-25T15:05:51.973 回答
0

实际上有一种方法可以做到这一点而无需递归,它允许您逐个字符地遍历整个表达式。这是时间和空间的 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
于 2020-10-17T04:55:59.347 回答
0

纯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>

于 2021-07-29T14:31:15.190 回答