数学パーサーへの条件文と関数の追加
https://stackoverflow.com/questions/3262889
-
16-09-2020 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私は、私が構築したバイナリツリーベースの数式パーサーを持っています。: (3.5 * 2) ^ 1 / (1 << 6).しかし、私はそれを少し拡張して、Cからのものをミラーリングして、三項選択演算子を追加したいと思います: {expr} ? {true-expr} : {false-expr}.私はまた、次のような機能を追加したいと思います sin(x) または ave(...).
しかし、私は（評価の仕組みのために）これをどのように処理するかについての手がかりを持っていないし、少なくとも非文法ベースの方法でこれをカバー
私のパーサーは現在、中置式を評価し、すぐにそれをツリーに変換することで動作し、そこからツリーを評価することができます。:そのあなたは標準式ツリーを沼地にします。
現在、私の評価者は次のようになります:
struct Node
{
int nType;
union
{
unsigned long dwOperator;
BOOL bValue;
int nValue; //for indices, args & functions
number_t fValue;
char* szValue; //for string literals to pass to functions
};
Node* pLeft;
Node* pRight;
};
number_t EvaluateTree(Node* pNode)
{
if(pNode == NULL)
return 0.0f;
int nType = pNode->nType;
if(nType == TOKEN_OPERATOR)
{
number_t fLeft = EvaluateTree(pNode->pLeft);
number_t fRight = EvaluateTree(pNode->pRight);
switch(pNode->dwOperator)
{
case '+': return fLeft + fRight;
case '-': return fLeft - fRight;
case '*': return fLeft * fRight;
case '/': return fLeft / fRight;
case '^': return pow(fLeft,fRight);
case '_': return pow(fLeft,1.0f/fRight);
case '%': return fmod(fLeft,fRight);
//case '?': return bSelect = ?;
//case ':': return (bSelect) ? fLeft : fRight;
//case '>': return fLeft > fRight;
//case '<': return fLeft < fRight;
//case '>=': return fLeft >= fRight;
//case '<=': return fLeft <= fRight;
//case '==': return fLeft == fRight;
//case '!=': return fLeft != fRight;
//case '||': return fLeft || fRight;
//case '&&': return fLeft && fRight;
case '&': return static_cast<number_t>(static_cast<unsigned long>(fLeft) & static_cast<unsigned long>(fRight));
case '|': return static_cast<number_t>(static_cast<unsigned long>(fLeft) | static_cast<unsigned long>(fRight));
case '~': return static_cast<number_t>(~static_cast<unsigned long>(fRight));
case '>>': return static_cast<number_t>(static_cast<unsigned long>(fLeft) >> static_cast<unsigned long>(fRight));
case '<<': return static_cast<number_t>(static_cast<unsigned long>(fLeft) << static_cast<unsigned long>(fRight));
default:
{
printf("ERROR: Invalid Operator Found\n");
return 0.0f;
}
}
}
else if(nType == TOKEN_NUMBER)
return pNode->fValue;
else if(nType == TOKEN_CALL)
return CreateCall(pNode); //not implemented
else if(nType == TOKEN_GLOBAL)
return GetGlobal(pNode);
else if(nType == TOKEN_ARGUMENT)
return GetArgument(pNode);
else if(nType == TOKEN_STRING)
return 0.0f;
return 0.0f;
}
どのように私はこれを達成することができます上の任意のヒント/ポインタ/アドバイスや有用なリンク？
例の小さなセット（要求されたように）:
私がすでに働いているもの
入力: 2 * (3 ^ 1.5) - 4 / (1 << 3)
出力: In-Order: 2.0 * 3.0 ^ 1.5 - 4.0 / 1.0 << 3.0
Pre-Order: - * 2.0 ^ 3.0 1.5 / 4.0 << 1.0 3.0
Post-Order: 2.0 3.0 1.5 ^ * 4.0 1.0 3.0 << / -
Result: 9.892304
私が追加したいもの
入力: (GetDay() == 31) ? -15.5 : 8.4
出力: 8.4
31日の出力: -15.5
入力: max([0],20) （ここで、[0]は引数0を示し、[0]=35）
出力: 20
入力: (GetField('employees','years_of_service',[0]) >= 10) ? 0.15 : 0.07 (ここで、[0]は引数0で、[0]は有効なインデックスに設定されます)
出力(emplyeeのyears_of_serviceが10未満の場合: 0.15
else出力: 0.07
引数は名前ではなくインデックスで渡され、文字列はdoubleではなく一重引用符でエスケープされることを除いて、基本的にいくつかのCに触発された
最後のビットが完了したら、ゲームや数学に依存するプログラムのようなものにこれを使用する予定なので、バイトコードをコンパイルするか、JITすることを望んでいます。入力セットのデータは一定ですが、入力セットは変更できますが、頻繁に使用されるため、「高速」である必要があり、非プログラマが使用できる必要があります。
解決
のために行うには正しいこと？と :パーサーによって生成されたツリーに依存します。パーサーが次のようなツリーを生成するふりをします
?
b :
t f
まず、スイッチの前にツリーを評価しない必要があり、ほとんどの場所で次のようなものを変更します
fLeft + fRight;
に
EvaluateTree(pNode->pLeft) + EvaluateTree(pNode->pRight);
+はすべてのさまざまな演算子に置き換えられます。
のために？:あなたがします。...
case ':': return 0.0f; /* this is an error in the parse tree */
case '?': if (!(pNode && pNode->pLeft && pNode->pRight &&
pNode->pRight->pLeft && pNode->pRight->pRight))
/* another error in the parse tree */
return 0.0f;
return EvaluateBool(pNode->pLeft) ?
EvaluateTree(pNode->pRight->pLeft) :
EvaluateTree(pNode->pRight->pRight) ;
EvaluateBoolの定義については、いくつかの選択肢があります。Cの方法は多かれ少なかれです
BOOL EvaluateBool(Node* pNode)
{
return (EvaluateTree(pNode) == 0.0) ? FALSE : TRUE;
}
次に、'の定義が必要です<'そして、falseの場合は0.0を返し、trueの場合は他の何かを返す友人。値-1は非常に一般的な真の値ですが、一般的にはブール値をintに格納するためのものです。
より構造化された方法は、'のようなすべての演算子を移動することです<'それはevaluateboolの本体にブール値を返し、EvaluateTreeのように多かれ少なかれ動作させます。
最後に、三項演算子を作る代わりに？:2つのノードを使用すると、ノード（およびパーサー）の定義を変更して最大3つのサブツリーを持つこともできますが、ほとんどの演算子は2つのツリーを持:三つ持っているだろう。たぶん何かのようなもの
case '?': return EvaluateBool(pNode->pLeft) ?
EvaluateTree(pNode->pMiddle) :
EvaluateTree(pNode->pRight) ;
しかし、その後、プリオーダー、インオーダー、ポストオーダーツリートラバーサルを書き直す必要があります。
第二部、機能。あなたがそれを行うことができる1つの方法は、関数の名前をszValueに格納することです。もう1つは、関数に応じてnTypeのさまざまな値の束を持つことです。パーサーでいくつかのルールを選択し、ここでインタプリタで使用する必要があります。あなたは何かのようなことをすることができます。..
else if(nType == TOKEN_CALL)
return EvaluateFunc(pNode);
次に、EvaluateFuncは次のようになります
number_t EvaluateFunc(Node* pNode)
{
if ((pNode == NULL) || (pNode->szValue == NULL))
return 0.0f;
if (0 == strcmp('cos', pNode->szValue))
return my_cos(EvaluateTree(pNode->pLeft));
else if (0 == strcmp('gcd', pNode->szValue))
return my_gcd(EvaluateTree(pNode->pLeft),
EvaluateTree(pNode->pRight));
/* etc */
else /* unknown function */ return 0.0f;
}
楽しいプロジェクトのように見えます、お楽しみください！
他のヒント
「PLeft」と「pRight」の代わりに、「Node」構造体を変更して子の配列を持つようにする必要があると思います。Sin()のような関数には、引数/子が1つあります。条件付き（三項）演算子には、3つの引数/子があります。
