4

私の MIPS アセンブリ クラスでは、未知のサイズの式を解析ツリーに読み込む必要がありました。私は木を扱う必要がなかったので、これが私が値を保存する方法でした:

ユーザーが式 1 + 3 - 4 を入力したとします (各オペランドは 1 から 9 の数字のみです)。

一番左の子ノードが開始点となり、2 つのデータが含まれます

1. The operand
2. Pointer to the next node (operator)

これが私がツリーを構築した方法です。読み込む値がなくなるまで、オペランドから演算子、次のオペランド、次の演算子へとポイントします。

私の次のタスクは、ツリーを再帰的にトラバースし、値を中置/前置/後置記法で出力することでした。

ツリーの構築方法を考えると、中置トラバーサルは問題ありませんでした。

私はプレフィックスにこだわっています。まず、私はそれを完全に理解していません。

プレフィックスで式 (1 + 3 - 4) を出力すると、- + 1 3 4 になりますか? オンラインの例に従うのに問題があります。

また、私のツリーは適切に構築されていると思いますか? つまり、現在のノードから前のノードに移動する方法がないということは、常に左端の子ノードからトラバーサルを開始する必要があるということです。

助けてくれてありがとう。

4

4 に答える 4

4

解析ツリーは次のようになります。

        「-」
         | |
     +---+---+
     | | | |
    「+」「4」
     | |
 +---+---+
 | | | |
'1' '3'

各ノードには 2 つのポインターがあります。1 つはその左の子に、もう 1 つはその右の子に。再帰トラバーサルを使用する場合、親ノードへのポインタは必要ありません。

ここにいくつかの擬似コードがあります:

中置表記のトラバーサル:

void traverse(Node *node) {
    if (node->leftChild != 0) {
        traverse(node->leftChild);
    }

    print(node->value);

    if (node->rightChild != 0) {
        traverse(node->rightChild);
    }
}

プレフィックス表記のトラバーサル:

void traverse(Node *node) {
    print(node->value);

    if (node->leftChild != 0) {
        traverse(node->leftChild);
    }

    if (node->rightChild != 0) {
        traverse(node->rightChild);
    }
}

後置表記のトラバーサル:

void traverse(Node *node) {
    if (node->leftChild != 0) {
        traverse(node->leftChild);
    }

    if (node->rightChild != 0) {
        traverse(node->rightChild);
    }

    print(node->value);
}

traverseツリーのルート ノードでメソッドを呼び出します。

データNode構造には次の 3 つのメンバーが必要です。

struct Node {
    char value;
    Node *leftChild;
    Node *rightChild;
}

ツリーの葉には、leftChildおよびのヌル ポインターが含まれますrightChild。

問題を理解してから、このコードをアセンブラに「翻訳」するために、このようなことを高水準言語 (使い慣れているものは何でも) で書くことが役立つ場合があります。このように、MIPS アセンブラーでブロック ワールドシミュレーションをプログラミングしたことを覚えています。

于 2009-02-07T15:51:54.227 に答える
3

一般に、すべてのリーフ ノード (子を持たないノード) がオペランドであり、内部ノード (それ以外のすべて) が演算子になるような方法でツリーを構築する必要があります。これは、演算子ノードの子がそのオペランドになるか、オペランドを持つ演算子になるようにする必要があります。この方法でツリーを構築できる場合、さまざまな表記法 (接頭辞、接尾辞、中置記号) の形成は非常に簡単です。よく知られているアルゴリズムがあるツリーの前順、後順、および順不同のトラバーサルに従うだけです。

私が知る限り、あなたはツリーを構築しているのではなく、リンクされたリストを構築しているので、これはうまくいきません。オペランドと演算子という 2 つの異なるエンティティがあり、それらを異なる方法で処理する必要があります。

于 2009-02-07T15:43:34.117 に答える
0

sikoraさんのおっしゃることに賛成です。この場合、スタックも使用できることを付け加えておきます。あなたの課題で特にツリーを使用する必要がある場合は、sykora の提案が最適です。ただし、単純な式の評価については、スタックの方がプログラミングしやすい場合があります。

于 2009-02-07T15:51:13.383 に答える
0

これは、解決済みの問題であるコンパイルの一般的な問題の例です。コンパイル手法についてグーグルで検索すると、問題に関連するあらゆる種類の情報が見つかります。

ライブラリには、Aho、Sethi、および Ullman によるCompilers: Principles, Techniques, and Toolsのコピーが必要です。ない場合は、購入を依頼してください（現場の標準作業です）。その最初の部分はあなたを助けるはずです。

第三版リンク

于 2009-02-07T15:59:35.973 に答える