2

私が構築したバイナリツリーベースの数式パーサーがあります。これは、次のような「通常の」数学に最適です(3.5 * 2) ^ 1 / (1 << 6)。ただし、 C: のものをミラーリングして、三項選択演算子を追加するために少し拡張したいと思います{expr} ? {true-expr} : {false-expr}。sin(x)やなどの機能も追加したいと思いave(...)ます。

ただし、これをどのように処理するかについての手がかりはありません（評価の仕組みのため）、少なくともグラマーベースではない方法でこれをカバーするものをWeb上で見つけることはできません（グラマーパーサージェネレーターを避けたいです）このため、可能であれば）。

私のパーサーは現在、中置式を評価し、すぐにツリーに変換することで機能します。その後、そこからツリーを評価できます。つまり、標準式ツリーをボグします。

現在、私の評価者は次のようになっています。

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

そうでなければ出力:0.07

引数が名前ではなくインデックスで渡され、文字列が double の代わりに一重引用符でエスケープされることを除いて、基本的には C にインスパイアされたいくつかの追加を伴う数学です。

最後のビットが完成したら、入力セットデータが一定であるが入力セットが変更できますが、頻繁に使用されるため、「高速」である必要があり、プログラマー以外でも使用できる必要があります。

4

2 に答える 2

1

のために行う正しいことは？and : パーサーによって生成されたツリーに依存します。パーサーが次のようなツリーを生成するふりをします

      ?
  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 は非常に一般的な真の値ですが、一般的に bool を int に格納する場合に使用されます。

より構造化された方法は、ブール値を返す「<」などのすべての演算子を Eva​​luateBool の本体に移動し、多かれ少なかれ EvaluateTree のように機能させることです。

最後に、三項演算子 ?: で 2 つのノードを使用する代わりに、ノード (およびパーサー) の定義を変更して、最大 3 つのサブツリーを持つようにすることもできます。その場合、ほとんどの演算子は 2 つのツリーを持つことになりますが、?: は 3 つのノードを持つことになります。 . 多分何かのような

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;
}

楽しい企画ですね、楽しんでください！

于 2010-07-18T21:25:49.773 に答える
1

「pLeft」と「pRight」ではなく、「Node」構造体を子の配列に変更する必要があると思います。sin() のような関数には、1 つの引数/子があります。条件 (三項) 演算子には 3 つの引数/子があります。

于 2010-07-18T22:01:54.940 に答える