3

私はコマンドライン計算機をやっているので、式を解析する必要があります。

calc 2*(3+4)*5

スキャナーのステップは既に完了しており、トークンの配列を返しています。今、私はパーサーのステップにいます。ただし、パーサー/式ツリーの実行方法についてはわかりません。

これは私がこれまで持っているすべてです：

NODE* create_node(TOKEN* t) {
    NODE* n = (NODE*)malloc(sizeof(NODE));
    n->t = t;
    n->l = n->r = 0;
    return n;
}

void insert_node(NODE** top, NODE** n) {
    if (!*top) {
        *top = *n;
        return;
    }

    if (!(*top)->l) insert_node(&(*top)->l, n);
    else
    if (!(*top)->r) insert_node(&(*top)->r, n);
    else
        insert_node(&(*top)->l, n);
}

次に、トークン配列を次のように渡します。

while (*tokens != 0) {
    NODE* n = create_node(*tokens++);
    insert_node(&root, &n);
}

ご覧のとおり、私のツリーは左に上がっています。上部の演算子による順序付けと、演算子の優先順位を含むリーフとしての番号の順序付けを行う方法がわかりません。

プログラミング（コード）の観点からも、啓発をいただければ幸いです。

4

3 に答える 3

8

ノードを作成するためのコードは私には問題ないように見えます。問題は、バイナリツリーを適切に構築する方法を理解するためのコードが必要なことです。NULLポインタを見つけた場所にノードを固定することはできません。

あなたの表現例：2*(3+4)*5

次のようなものになります：

    *
   / \
  *   5
 / \
2   +
   / \
  3   4

あなたの先生はあなたにこれをする方法のいくつかの考えを与えるべきでした。

私が大学にいたとき、私はこの種のコードを書き、私たちは独自の「再帰下降パーサー」を書きました。もう1つの一般的なアプローチは、GNUBisonのようなシステムを使用することです。

メモを確認して、先生がこれについて何を言ったかを確認し、本当にわからないかどうか先生に尋ねる必要があります。

http://en.wikipedia.org/wiki/Recursive_descent_parser

http://en.wikipedia.org/wiki/GNU_bison

于 2012-06-13T23:25:17.780 に答える
0

の C++ 実装については、これらのリンクを参照してください。

  1. 後置パーサーへのインフィックス
  2. バイナリ式ツリー パーサーへのインフィックス

前述のように、両方の実装でスタックが使用されます。二分式ツリーへのインフィックスの場合、2 つのスタックが使用されます。1 つは演算子用で、もう 1 つはオペランド用です。

于 2012-12-18T14:38:49.680 に答える