C++ 多项式分词器

Question

我目前正在创建一个分词器，它将多项式作为字符串并输出多项式中的单项式数组（单个项）。

例如：

输入：4x^2+3x^-2+2

输出：{ "4x^2", "3x^-2", "2" }

我不确定从哪里开始，因为多项式由于异常而有点棘手。任何人都可以提供任何见解吗？

Answer 1

这里可能有一些可以使用正则表达式或模式匹配来完成的快速而肮脏的技巧。

但是，实现此解析的可靠方法是使用我们优秀的高等教育机构已经（或应该）教授的标准工具。或者，至少他们在我的时代。当然，我指的是 lexical analyzers and LALR(1) parser generators.

词法分析器，例如 flex，采用正则表达式形式的标记定义列表，并生成对输入流进行标记化的代码。在这种情况下，以下简单的 flex 规则集应该足以标记您的多项式，我认为：

%{
#include "y.tab.h"
%}

digit         [0-9]
letter        [a-zA-Z]

%%
"+"                  { return PLUS;       }
"-"                  { return MINUS;      }
"*"                  { return TIMES;      }
"/"                  { return SLASH;      }
"^"                  { return EXPONENT;   }
{letter}+ {
                       yylval.id = strdup(yytext);
                       return IDENT;      }
{digit}+             { yylval.num = atoi(yytext);
                       return NUMBER;     }

这将执行初始任务，即从您的输入字符串中解析出多项式的各个元素。

词法分析器与LALR(1)解析器生成器一起工作，例如bison，它生成y.tab.h定义要解析的语法的文件，以及y.tab.h中的元素语法，例如 PLUS、MINUS 和所有其他标记。

Bison 采用上下文无关文法的规范，并为其生成解析器。语法规范，即使对于像这样的简单多项式，也往往相当详细，因此这只是多项式语法规范的一个子集：

polynomial: additive_expression;

additive_expression: additive_term
                   | additive_expression plus_or_minus additive_term

plus_or_minus: PLUS | MINUS;

/* additive_term then fleshes out the structure of each polynomial term */

当然，这将通过构建解析树作为规则集的一部分的代码片段来补充。

flex 和 bison 已经存在了很长时间，最初生成 C 代码（因此我的 flex 示例中的 C 片段）；但目前也能够生成 C++ 代码。不用说，如果您不熟悉这些工具，学习曲线会很陡峭；但这是为非平凡语法（例如多项式）实现解析器的经过时间考验的方法。

C++ 多项式分词器

C++ Polynomial Tokenizer

c++

polynomials