logo标签列表

编写一个简单的方程解析器

c++algorithmparsing
16

用什么样的算法可以实现这个功能（例如，给定一个字符串，如何找到答案）：

((5 + (3 + (7 * 2))) - (8 * 9)) / 72

如果有人写了这样的东西，我该如何处理这么多嵌套的括号？

请查看我的<a href="https://dev59.com/v3E95IYBdhLWcg3wlu6z#2336769">关于如何编写自顶向下递归下降解析器的Stack Overflow答案</a>。这种方法对于表达式非常简单。 - Ira Baxter
这是一个表达式而不是方程。http://www.mathnstuff.com/math/algebra/aequex.htm 或 https://en.m.wikipedia.org/wiki/Equation - nodebase
10个回答
23

你可以使用逆波兰表达式或逆波兰式, 两者都使用栈来处理此问题，维基百科比我说得更好。

来自维基百科，

While there are tokens to be read:

    Read a token.
    If the token is a number, then add it to the output queue.
    If the token is a function token, then push it onto the stack.
    If the token is a function argument separator (e.g., a comma):

        Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue. If no left parentheses are encountered, either the separator was misplaced or parentheses were mismatched.

    If the token is an operator, o1, then:

        while there is an operator token, o2, at the top of the stack, and

                either o1 is left-associative and its precedence is less than or equal to that of o2,
                or o1 is right-associative and its precedence is less than that of o2,

            pop o2 off the stack, onto the output queue;

        push o1 onto the stack.

    If the token is a left parenthesis, then push it onto the stack.
    If the token is a right parenthesis:

        Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
        Pop the left parenthesis from the stack, but not onto the output queue.
        If the token at the top of the stack is a function token, pop it onto the output queue.
        If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.

When there are no more tokens to read:

    While there are still operator tokens in the stack:

        If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses.
        Pop the operator onto the output queue.

Exit.
请参考以下链接：http://social.msdn.microsoft.com/Forums/en-US/csharplanguage/thread/31ac96da-415e-424b-9e1f-6aec86c4c3ae。 - Mou
5

最简单的解决方法是实现Shunting Yard算法，将表达式从中缀表达式转换为后缀表达式。

评估后缀表达式非常容易。

Shunting Yard算法可以在不到30行代码的情况下实现。您还需要对输入进行标记化（将字符字符串转换为操作数、运算符和标点符号的序列），但编写一个简单的状态机来完成这项工作是直接的。

3
詹姆斯提供了一个很好的答案。维基百科上也有一篇很好的文章。
如果（我不建议这样做）你想直接解析该表达式，因为每个括号集中最多只有一对操作数，所以可以采用以下方法：
解析到第一个“)”。然后解析回前一个“（”。评估里面的内容并替换整个集合为一个值。然后递归重复此过程，直到完成。
所以在这个例子中，你首先会解析“(7 * 2)”并将其替换为14。 然后你会得到(3 + 14)，并将其替换为17。 依此类推。
你可以使用Regex甚至是IndexOf和Substring来完成这个任务。
我没有检查语法，但大概是这样：
int y = string.IndexOf(")");  
int x = string.Substring(0,y).LastIndexOf("(");  
string z = string.Substring(x+1,y-x-1) // This should result in "7 * 2"

你需要评估生成的表达式并循环执行，直到括号用尽，然后评估字符串的最后一部分。
那么，如果你喜欢詹姆斯的回答，为什么不点赞呢？;-) - C. K. Young
因为我昨天刚开始贡献，还没有所需的15声望，否则我会有的。当然你可以帮忙 :) - nycdan
2
我会使用几乎在任何地方都可以使用的工具。
我喜欢lex/yacc，因为我熟悉它们，但是其他地方也有类似的工具。因此，在编写复杂代码之前，请查看是否有可以帮助您简化代码的工具（这类问题以前已经解决过了，所以不要重复造轮子）。
因此，使用lex（flex）/yacc（bison），我会执行以下操作：

e.l

%option noyywrap

Number      [0-9]+
WhiteSpace  [ \t\v\r]+
NewLine     \n
%{
#include <stdio.h>
%}

%%

\(              return '(';
\)              return ')';
\+              return '+';
\-              return '-';
\*              return '*';
\/              return '/';

{Number}        return 'N';
{NewLine}       return '\n';
{WhiteSpace}    /* Ignore */

.               fprintf(stdout,"Error\n");exit(1);


%%

e.y

%{
#include <stdio.h>
    typedef double (*Operator)(double,double);
    double mulOp(double l,double r)  {return l*r;}
    double divOp(double l,double r)  {return l/r;}
    double addOp(double l,double r)  {return l+r;}
    double subOp(double l,double r)  {return l-r;}
extern char* yytext;
extern void yyerror(char const * msg);
%}

%union          
{
    Operator        op;
    double          value;
}

%type   <op>        MultOp AddOp
%type   <value>     Expression MultExpr AddExpr BraceExpr

%%

Value:          Expression '\n'   { fprintf(stdout, "Result: %le\n", $1);return 0; }

Expression:     AddExpr                          { $$ = $1;}

AddExpr:        MultExpr                         { $$ = $1;}
            |   AddExpr   AddOp  MultExpr        { $$ = ($2)($1, $3);}

MultExpr:       BraceExpr                        { $$ = $1;}
            |   MultExpr  MultOp BraceExpr       { $$ = ($2)($1, $3);}

BraceExpr:      '(' Expression ')'               { $$ = $2;}
            |   'N'                              { sscanf(yytext,"%le", &$$);}

MultOp:         '*'                              { $$ = &mulOp;}
            |   '/'                              { $$ = &divOp;}
AddOp:          '+'                              { $$ = &addOp;}
            |   '-'                              { $$ = &subOp;}
%%

void yyerror(char const * msg)
{
    fprintf(stdout,"Error: %s", msg);
}
 
int main()
{
    yyparse();
}

构建

> flex e.l
> bison e.y
> gcc *.c
> ./a.out
((5 + (3 + (7 * 2))) - (8 * 9)) / 72
Result: -6.944444e-01
>

上述内容还处理了常规运算符优先级规则：
这不是因为我做了什么，而是有一些聪明的人早在很久以前就已经解决了这个问题，现在你可以轻松地获取表达式解析的语法规则（只需搜索 C语法 并提取所需部分）。
> ./a.out
2 + 3 * 4
Result: 1.400000e+01
2
你可以使用状态机解析器（yacc LALR等）或递归下降解析器来实现。解析器可以发出逆波兰标记以供以后评估或编译。或者，在即时解释器实现中，递归下降解析器可以在从叶子标记返回时动态计算子表达式，并最终得出结果。
0
如果表达式已知是完全括号化的（即，所有可能的括号都在那里），那么可以使用递归下降解析轻松完成此操作。基本上，每个表达式都是以下形式之一：
 number

或者是这种形式

 (expression operator expression)

这两种情况可以通过它们的第一个标记进行区分，因此简单的递归下降就足够了。实际上，我曾经看到过这个确切的问题被用作测试入门编程课程中递归思维的方法。

如果您不一定有这个保证，那么某种形式的优先级解析可能是一个好主意。这个问题的许多其他答案都讨论了各种算法的不同风味。

0

是的，算法是Shunting yard algorithm，但如果你想要实现它，我建议你使用Python和它的编译器包

import compiler
equation = "((5 + (3 + (7 * 2))) - (8 * 9)) / 72"
parsed = compiler.parse( equation )

print parsed

您还可以使用内置的eval()方法来评估此表达式

print eval("5 + (4./3) * 9") // 17
0

首先将表达式转换成前缀或后缀形式。然后，它就非常容易进行评估了！

例如：

后缀表达式求值。

0
什么？不要写解析器，除非这是一项作业任务。市面上已经有很多解析器了，它们的优势在于已经存在，你不需要自己编写。与所有其他建议相比，市场中的解析器都具有最大的优势。
-2

或者你可以在R中只用一行代码来完成这个操作：

> eval(parse(text = '((5 + (3 + (7*2))) - (8 * 9))/72' ))
[1] -0.6944444
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接