我目前正致力于创建一个将多项式作为字符串并在多项式内输出单项式(单项)的数组的标记器。C++多项式Tokenizer
例如:
输入:4x^2+3x^-2+2
输出:{ "4x^2", "3x^-2", "2" }
我不完全知道从哪里问候开始这是由于这样的事实,多项式多一点麻烦,由于异常。任何人都可以提供任何见解吗?
我目前正致力于创建一个将多项式作为字符串并在多项式内输出单项式(单项)的数组的标记器。C++多项式Tokenizer
例如:
输入:4x^2+3x^-2+2
输出:{ "4x^2", "3x^-2", "2" }
我不完全知道从哪里问候开始这是由于这样的事实,多项式多一点麻烦,由于异常。任何人都可以提供任何见解吗?
这里可能会有一些使用正则表达式或模式匹配的快速和肮脏的黑客攻击。
但是,实现这种解析的可靠方法是使用已经(或应该已经)在我们的高等院校教授的标准工具。或者,至少他们是在我的时间。我当然是指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
文件定义语法被解析,并在语法的元素,如,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++代码。不言而喻,如果你对这些工具不熟悉,将会有一个陡峭的学习曲线;但是这是用于实现非平凡语法的解析器的经过时间考验的方式,例如多项式。
难道你不能只加分/加减,然后修剪空白?另外,多项式不能具有负的权力。一旦你允许负面的权力,它基本上相当于正则表达式的空间,这是一个不同的(严格来说更大的)空间。 –
我可以但指数可以是负数,我不知道如何解释。 – star
使用正则表达式(正则表达式)。 – 1201ProgramAlarm