我已经开发了一种使用简单堆栈算法的方程式解析器，该算法将处理二进制(+，-，|，＆，*，/等)运算符，一元(！)运算符和括号。

但是，尽管可以使用括号来强制使用优先级，但是使用此方法会使所有优先级从左到右的东西都具有相同的优先级。

因此，现在" 1 + 11 * 5"返回60，而不是人们期望的56.

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

为清楚起见进行了编辑：

解析具有优先级的方程的最佳算法是什么？

我对一些易于实现的东西感兴趣，并且了解我可以自己编写代码，以避免可用代码的许可问题。

语法：

我不明白我用手写的语法问题。很简单，我认为不需要YACC或者Bison。我只需要使用诸如" 2 + 3 *(42/13)"之类的方程式来计算字符串。

语言：

我正在用C进行此操作，但是我对算法感兴趣，而不对特定于语言的解决方案感兴趣。 C足够低，因此如果需要，可以很容易地将其转换为另一种语言。

程式码范例

我在上面发布了简单表达式解析器的测试代码。项目需求发生了变化，因此我不需要针对性能或者空间进行代码优化，因为它没有合并到项目中。它采用原始的冗长形式，应该易于理解。如果我在运算符优先级方面做进一步的事情，我可能会选择宏技巧，因为它可以简单地与程序的其余部分匹配。但是，如果我在实际项目中使用过它，那么我将寻求一个更紧凑/更快速的解析器。

相关问题

Smart design of a math parser?

-亚当

解决方案

回答

如果可以描述我们当前正在使用的语法，这将有所帮助。听起来问题可能出在这里！

编辑：

我们不理解语法问题，并且"我们已经手工编写了"这一事实很可能解释了为什么我们对格式为" 1 + 11 * 5"的表达式(例如，运算符优先级)有疑问。例如，对"算术表达式的语法"进行谷歌搜索应该会产生一些好的指针。这样的语法不必太复杂：

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

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

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

例如，可以做到这一点，并且可以进行微不足道的扩展，以处理一些更复杂的表达式(例如，包括函数或者幂，...)。

例如，我建议我们看一下该线程。

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

请注意，使用语法根本不意味着使用特定工具(如la Yacc，Bison等)。实际上，我们肯定已经在使用以下语法：

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

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

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

(或者类似的东西)而不知道！

回答

我们想使用一种语言吗？ ANTLR将使我们从Java的角度进行操作。阿德里安·库恩(Adrian Kuhn)撰写了一篇出色的文章，内容涉及如何在Ruby中编写可执行语法。实际上，他的例子几乎就是算术表达式例子。

回答

这取决于我们希望它有多"通用"。

如果我们希望它真的非常通用，例如能够解析数学函数，例如sin(4 + 5)* cos(7 ^ 3)，则可能需要一个解析树。

其中，我认为不适合在此处粘贴完整的实现。我建议我们查看其中一本臭名昭著的"龙书"。

但是，如果我们只想要优先支持，则可以通过将表达式转换为后缀形式来实现，在这种形式中，可以从Google获得可以复制粘贴的算法，或者我认为我们可以使用二进制代码自行编写树。

当我们以postfix形式使用它时，从那时起这只是小菜一碟，因为我们已经了解了堆栈如何提供帮助。

回答

艰难的道路

我们需要递归下降解析器。

要获得优先权，我们需要进行递归思考，例如，使用示例字符串，

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等)。

通常，我们可以运行一些野牛样本代码，并获得所需的C代码来演示这四个功能的计算器：

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

查看生成的代码，发现这并不像听起来那样简单。同样，使用像Bison这样的工具的优点是：1)学到一些东西(特别是如果我们阅读了Dragon书籍并学习了语法)，2)避免了NIH尝试重新发明轮子。使用真正的解析器生成器工具，我们实际上希望以后再扩展，向其他人展示解析器是解析工具的领域。

更新：

这里的人们提供了很多合理的建议。关于避免跳过解析工具或者仅使用Shunting Yard算法或者手推递归递归解析器的唯一警告是，很少有玩具语言有一天可能会变成具有功能(正弦，余弦，对数)以及变量，条件和for循环的大型实际语言。 。

对于小型，简单的解释器而言，Flex / Bison可能会显得过大，但是当需要进行更改或者添加功能时，脱离分析器+评估器可能会带来麻烦。情况会有所不同，我们将需要运用自己的判断力；只是不要为自己的罪过惩罚别人[2]并建立一个不够充分的工具。

我最喜欢的解析工具

世界上最好的工具是Parsec库(用于递归的体面解析器)，该库随附了编程语言Haskell。它看起来很像BNF，或者像某些专用工具或者特定于域的语言进行解析(示例代码[3])，但实际上它只是Haskell中的常规库，这意味着它与其余代码在同一构建步骤中进行编译我们可以编写任意Haskell代码并在解析器中调用它，也可以在同一代码中混合和匹配其他库。 (顺便说一下，将这样的解析语言嵌入Haskell之外的语言中会导致大量的语法混乱。我在Cand中做到了这一点，效果很好，但不是那么简洁。)

笔记：

1理查德·斯托曼(Richard Stallman)在《为什么不应该使用Tcl》中说

The principal lesson of Emacs is that
  a language for extensions should not
  be a mere "extension language".  It
  should be a real programming language,
  designed for writing and maintaining
  substantial programs. Because people
  will want to do that!

[2]是的，使用该"语言"让我永远感到害怕。

还要注意，当我提交此条目时，预览是正确的，但是SO不足以解析我在第一段中的紧密锚标记，这证明了解析器并不是一件容易的事，因为如果我们使用正则表达式和一些骇客技巧，可能会出现一些细微的错误。

[3]使用Parsec的Haskell解析器的代码段：一个四函数计算器，扩展了指数，括号，用于乘法的空格和常量(如pi和e)。

aexpr   =   expr `chainl1` toOp
expr    =   optChainl1 term addop (toScalar 0)
term    =   factor `chainl1` mulop
factor  =   sexpr  `chainr1` powop
sexpr   =   parens aexpr
        <|> scalar
        <|> ident

powop   =   sym "^" >>= return . (B Pow)
        <|> sym "^-" >>= return . (\x y -> B Pow x (B Sub (toScalar 0) y))

toOp    =   sym "->" >>= return . (B To)

mulop   =   sym "*" >>= return . (B Mul)
        <|> sym "/" >>= return . (B Div)
        <|> sym "%" >>= return . (B Mod)
        <|>             return . (B Mul)

addop   =   sym "+" >>= return . (B Add) 
        <|> sym "-" >>= return . (B Sub)

scalar = number >>= return . toScalar

ident  = literal >>= return . Lit

parens p = do
             lparen
             result <- p
             rparen
             return result

回答

我建议作弊并使用分流场算法。这是编写简单的计算器类型的解析器的一种简便方法，并且考虑了优先级。

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

回答

调车场算法是解决此问题的正确工具。维基百科对此确实感到困惑，但基本上该算法的工作原理如下：

假设我们要评估1 + 2 * 3 +4. 直觉上，我们"知道"我们必须先进行2 * 3，但是如何获得此结果？关键是要认识到，当我们从左到右扫描字符串时，当跟随它的运算符的优先级较低(或者等于)时，我们将评估一个运算符。在该示例的上下文中，这是我们要执行的操作：

• 看一下：1 + 2，什么也不做。
• 现在看1 + 2 * 3，什么都不做。
• 现在来看1 + 2 * 3 + 4，现在我们知道必须评估2 * 3，因为下一个运算符的优先级较低。

我们如何实施呢？

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

回到该示例，它的工作方式如下：

N = []
行动= []

• 读取1. N = [1]，Ops = []
• 阅读+。 N = [1]，操作数= [+]
• 读取2. N = [1 2]，操作数= [+]
• 阅读*。 N = [1 2]，操作数= [+ *]
• 读3. N = [1 2 3]，Ops = [+ *]
• " +"保持关联状态，因此我们也想将1、6弹出，然后执行+。 N = [7]，操作数= []。
• 最后，将[+]推入运算符堆栈。 N = [7]，操作数= [+]。
• 读4. N = [7 4]。行动= [+]。
• 输入用完了，所以现在要清空堆栈。得到的结果是11.

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

回答

很久以前，我制定了自己的解析算法，这在任何有关解析的书(例如《龙书》)中都找不到。看看Shunting Yard算法的指针，我确实看到了相似之处。

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

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

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

我们可以在http://users.telenet.be/bartl/expressionParser/expressionParser.html上找到实时演示。

// operator table
var ops = {
   '+'  : {op: '+', precedence: 10, assoc: 'L', exec: function(l,r) { return l+r; } },
   '-'  : {op: '-', precedence: 10, assoc: 'L', exec: function(l,r) { return l-r; } },
   '*'  : {op: '*', precedence: 20, assoc: 'L', exec: function(l,r) { return l*r; } },
   '/'  : {op: '/', precedence: 20, assoc: 'L', exec: function(l,r) { return l/r; } },
   '**' : {op: '**', precedence: 30, assoc: 'R', exec: function(l,r) { return Math.pow(l,r); } }
};

// constants or variables
var vars = { e: Math.exp(1), pi: Math.atan2(1,1)*4 };

// input for parsing
// var r = { string: '123.45+33*8', offset: 0 };
// r is passed by reference: any change in r.offset is returned to the caller
// functions return the parsed/calculated value
function parseVal(r) {
    var startOffset = r.offset;
    var value;
    var m;
    // floating point number
    // example of parsing ("lexing") without aid of regular expressions
    value = 0;
    while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++;
    if(r.string.substr(r.offset, 1) == ".") {
        r.offset++;
        while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++;
    }
    if(r.offset > startOffset) {  // did that work?
        // OK, so I'm lazy...
        return parseFloat(r.string.substr(startOffset, r.offset-startOffset));
    } else if(r.string.substr(r.offset, 1) == "+") {  // unary plus
        r.offset++;
        return parseVal(r);
    } else if(r.string.substr(r.offset, 1) == "-") {  // unary minus
        r.offset++;
        return negate(parseVal(r));
    } else if(r.string.substr(r.offset, 1) == "(") {  // expression in parens
        r.offset++;   // eat "("
        value = parseExpr(r);
        if(r.string.substr(r.offset, 1) == ")") {
            r.offset++;
            return value;
        }
        r.error = "Parsing error: ')' expected";
        throw 'parseError';
    } else if(m = /^[a-z_][a-z0-9_]*/i.exec(r.string.substr(r.offset))) {  // variable/constant name        
        // sorry for the regular expression, but I'm too lazy to manually build a varname lexer
        var name = m[0];  // matched string
        r.offset += name.length;
        if(name in vars) return vars[name];  // I know that thing!
        r.error = "Semantic error: unknown variable '" + name + "'";
        throw 'unknownVar';        
    } else {
        if(r.string.length == r.offset) {
            r.error = 'Parsing error at end of string: value expected';
            throw 'valueMissing';
        } else  {
            r.error = "Parsing error: unrecognized value";
            throw 'valueNotParsed';
        }
    }
}

function negate (value) {
    return -value;
}

function parseOp(r) {
    if(r.string.substr(r.offset,2) == '**') {
        r.offset += 2;
        return ops['**'];
    }
    if("+-*/".indexOf(r.string.substr(r.offset,1)) >= 0)
        return ops[r.string.substr(r.offset++, 1)];
    return null;
}

function parseExpr(r) {
    var stack = [{precedence: 0, assoc: 'L'}];
    var op;
    var value = parseVal(r);  // first value on the left
    for(;;){
        op = parseOp(r) || {precedence: 0, assoc: 'L'}; 
        while(op.precedence < stack[stack.length-1].precedence ||
              (op.precedence == stack[stack.length-1].precedence && op.assoc == 'L')) {  
            // precedence op is too low, calculate with what we've got on the left, first
            var tos = stack.pop();
            if(!tos.exec) return value;  // end  reached
            // do the calculation ("reduce"), producing a new value
            value = tos.exec(tos.value, value);
        }
        // store on stack and continue parsing ("shift")
        stack.push({op: op.op, precedence: op.precedence, assoc: op.assoc, exec: op.exec, value: value});
        value = parseVal(r);  // value on the right
    }
}

function parse (string) {   // wrapper
    var r = {string: string, offset: 0};
    try {
        var value = parseExpr(r);
        if(r.offset < r.string.length){
          r.error = 'Syntax error: junk found at offset ' + r.offset;
            throw 'trailingJunk';
        }
        return value;
    } catch(e) {
        alert(r.error + ' (' + e + '):\n' + r.string.substr(0, r.offset) + '<*>' + r.string.substr(r.offset));
        return;
    }    
}

回答

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

回答

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

回答

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

回答

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

回答

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

Harold  writes:
  
  
    I remember reading, a long time ago, of an algorithm that converted
    algebraic expressions to RPN for easy evaluation. Each infix value or
    operator or parenthesis was represented by a railroad car on a
    track. One
    type of car split off to another track and the other continued straight
    ahead. I don't recall the details (obviously!), but always thought it
    would be interesting to code. This is back when I was writing 6800 (not
    68000) assembly code.

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

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

开始：令牌" 1"：isnumber，放入
pstack(push)令牌'+'：isoperator
如果优先级<，则设置优先级= 2
then_operator_precedence然后
reduce()//参见下文，将" +"放入
pstack(push)令牌'2'：isnumber，

放入pstack(push)令牌'*'中：
isoperator，设置优先级= 1，放入
pstack(push)//检查优先级为
//在令牌'3'上方：isnumber，放入
pstack(push)输入结束，需要
减少(目标是空的pstack)reduce()
//完毕

减少推送中的弹出元素
堆叠并放入结果中
堆叠时，请始终交换前两个项目
pstack，如果它们是形式
'操作员''编号'：

pstack：'1''+''2''''3'rstack：()
... pstack：()rstack：'3''2''''1'
'+'

如果表达式是：

1 * 2 + 3

那么减少触发将有
读取令牌" +"
其优先级低于
'*'已经被推送，所以它应该有
完毕：

pstack：'1''''2'rstack：()...
pstack：()rstack：'1''2'''

然后按" +"，再按" 3"，然后
然后终于减少：

pstack：'+''3'rstack：'1''2'''
... pstack：()rstack：'1''2'''3'
'+'

所以简短的版本是：推送号码，
推动操作员时检查
前一个运算符的优先级。
如果高于操作员的
首先要推动
减少，然后推动电流
操作员。要处理parens，只需保存
"上一个"的优先顺序
运算符，并在pstack上标记
告诉减少算法
解决内部问题时停止减少
对的一对。闭幕式
触发减少，最终也会减少
输入，也删除了打开的
从pstack中删除标记，并且
恢复"上一个操作"
优先级，以便解析可以继续
在关闭的地方之后
离开。这可以通过递归来完成
是否(提示：使用堆栈来存储
先前的优先级
遇到'('...)这
这是通用版本
实现的解析器生成器
调车场算法使用
yacc或者bison或者taccle(tcl类似物
yacc)。

彼德

回答

-亚当

我已经在我的网站上发布了一个超紧凑型(1类，<10 KiB)Java Math Evaluator的源代码。这是一种递归下降解析器，其类型为引起已接受答案的发布者颅骨爆炸。

回答

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

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

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

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

调用为：

回答

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

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

回答

我们是否考虑过使用Boost Spirit？它使我们可以像这样在C ++中编写类似EBNF的语法：

回答

可以在这里找到使用pyparsing的Python解决方案。使用各种具有优先级的运算符来解析中缀表示法是相当普遍的，因此pyparsing还包括operatorPrecedence表达式构建器。使用它，我们可以轻松地使用例如" AND"，" OR"，" NOT"来定义布尔表达式。或者，我们可以扩展四功能算术以使用其他运算符，例如！对于阶乘，对于模数为"％"，或者添加P和C运算符以计算排列和组合。我们可以编写一个用于矩阵符号的中缀解析器，其中包括对" -1"或者" T"运算符的处理(用于反转和转置)。这里是一个四功能解析器(带有"！"的意思)的operatorPrecedence示例，而功能更全的解析器和评估器在此处。

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

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

对不同方法的很好解释：

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

段落数量不匹配