c - 如何实现具有优先级和结合性的中缀计算器

Question

我正在测试使用 bison flex 编写中缀计算器的示例。我发现除了括号“()”之外，其他都正确。我发现当我输入带括号的计算时，计算结果不正确。这是文件“infix-calc.y”的代码

/* bison grammar file for infix notation calculator */
%{
#define YYSTYPE double
#include <math.h>
#include <stdio.h>


int yyerror(const char *s);
int yylex(void);


%}

%token NUM
%left '-' '+'
%left '*' '/'
%left NEG
%right '^'

%% /* Grammer rules and actions follow */

input: /* empty */
     | input line
     ;

line: '\n'
    | exp '\n' { printf("\t%.10g\n", $1); }
    ;

exp: NUM { $$ = $1; }
   | exp '+' exp { $$ = $1 + $3; }
   | exp '-' exp { $$ = $1 - $3; }
   | exp '*' exp { $$ = $1 * $3; }
   | exp '/' exp { $$ = $1 / $3; }
   | '-' exp %prec NEG { $$ = -$2; }
   | exp '^' exp { $$ = pow($1, $3); }
   | '(' exp ')' { $$ = $2; }
   ;

%%

/* Additional C code */

int main() { return yyparse(); }

int yyerror(const char* s)
{
    printf("%s\n", s);
    return 0;
}

这里是文件“infix-calc.lex”的代码

/* lex file for infix notation calculator */
%option noyywrap

%{
#define YYSTYPE double     /* type for bison's var: yylval */
#include <stdlib.h>        /* for atof(const char*) */
#include "infix-calc.tab.h"
%}


digits [0-9]
rn     (0|[1-9]+{digits}*)\.?{digits}*
op     [+*^/\-]
ws     [ \t]+  


%%

{rn}   yylval = atof(yytext); return NUM;
{op}   |
\n     return *yytext;
{ws}   /* eats up white spaces */

%%

问题是，当我输入“2 * (3 + 4)”时，我应该会收到输出“14”。但是输入的是“() 10”。在这种情况下，括号似乎不起作用。这些代码有什么问题？非常感谢大家对我的帮助!!!!

Answer 1

看起来您必须将 ( 和 ) 声明为标记才能使其正常工作。

在您的 lex 文件中的最后一个 %% 之前添加以下两行:

"("    return LEFT;
")"    return RIGHT;

然后添加

%token LEFT RIGHT

到infix-calc.y的顶部，并替换

   | '(' exp ')' { $$ = $2; }

与

   | LEFT exp RIGHT { $$ = $2; }