C++ 多项式分词器

Question

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

例如:

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

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

我不确定从哪里开始，因为多项式由于异常而有点棘手。谁能给我任何见解？

Answer 1

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

但是，实现此解析的可靠方法是使用我们优秀的高等教育机构已经(或应该)教授的标准工具。或者，至少他们在我的时代。当然，我指的是 lexical analyzers和 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 文件，以及语法中的元素，如 PLUS、MINUS和所有其他 token 。

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++ 代码。不用说，如果您不熟悉这些工具，学习曲线会很陡峭；但这是为非平凡语法(例如多项式)实现解析器的耗时考验的方法。