我目前正致力於創建一個將多項式作爲字符串並在多項式內輸出單項式(單項)的數組的標記器。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