木とプレフィックス（ポーランド）表記については？

StackOverflow https://stackoverflow.com/questions/523957

質問

私のMIPSアセンブリのクラスを解析したツリーに、未知の大きさの表現で読むために私を必要としました。私は木に対処しなければならなかったことがありませんので、私は値を格納周りに行ってきましたどのようにこれは、次のとおりです。

は、ユーザが式1 + 3入力と言うことができます - 4（各オペランドのみ桁であってもよい1-9）

私の一番左の子ノードが出発点になると、データの2枚が含まれています。

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

これは私が木を構築する方法です。値が読まれるべきで左これ以上はなかったまで、私は次のオペレータに次のオペランドにオペレータにオペランドから指すことになります。

私の次のタスクは、再帰的にツリーをトラバースすることで、出力インフィックス/プリフィックス/ポストフィックス表記の値

中置トラバーサルは、私は私のツリーを構築方法を検討全く問題なかった。

私は、接頭辞にこだわっています。まず、私は完全にそれを理解していない。

するとき、私は、出力たちの表現 - 接頭辞で（1 + 3 4）それが出てくるはずです - + 1 3 4？私はオンラインの例以下の問題を抱えています。

また、あなたは私のツリーが適切に構築されると思いますか？私が意味する、私はいつも直感的に私のTAは、それが進むべき道であると言いましたにもかかわらず、右鳴らない左端の子ノードからトラバースを開始しなければならないことを意味現在のノードから、前のノードに移動する方法がありません。

任意の助けをありがとうございました。

役に立ちましたか？

解決

あなたのパースツリーは次のようになります。 

        '-'
         |
     +---+---+
     |       |
    '+'     '4'
     |
 +---+---+
 |       |
'1'     '3'

各ノードには、二つのポインタを持っています。その左の子の一つとその右の子に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にnullポインタを含んでいるでしょう。

時にはそれが問題を理解して、アセンブラにこのコードを「翻訳」する（あなたが快適に感じるものは何でも）は、より高いレベルの言語でのこのようなものを書くことができます。私はこのようなMIPSアセンブラでブロックの世界のシミュレーションをプログラミング覚えています。

他のヒント

一般的に、あなたはすべてのリーフノード（子を持たないもの）のオペランドであり、内部ノード（他のすべて）が事業者であるようにツリーを構築する必要があります。これは、オペレータノードの子がそのオペランド、または自分自身のオペランドを持つ演算子であるようにする必要があります。あなたは様々な表記（接頭辞、接尾辞、中置）を形成し、このようにツリーを構築することができれば、かなり簡単です - あなただけの前順、後順とそのためによく知られたアルゴリズムがある木のトラバース、順序どおりに従ってください。

私の知る限り、あなたは木、むしろリンクリストを構築していない、これはあなたによく奉仕するつもりはありません。オペランドと演算子 - - あなたは2つの異なるエンティティを持っているあなたは違ったそれらを扱うために持っている。

。

私はsykoraが言うことに同意します。私はあなたがこの場合にもスタックを使用することができることを追加したいと思います。あなたの割り当ては、具体的ツリーを使用する必要があるなら、その後、sykoraの提案は、最高動作します。ただし、スタックは、単純な式の評価のためにプログラムする方が簡単かもしれません。

これは解決される問題である、コンパイルの一般的な問題のインスタンスです。あなたがコンパイル技術にグーグルを行う場合、あなたの問題に関連する情報のすべての種類を見つけるでしょう。

アホ、セティ、およびウルマンによって原則、テクニック、およびツールの

あなたのライブラリーは、のコンパイラのコピーを持っている必要があります。それはそれを持っていない場合、（それはフィールドの標準作業です）購入のためにそれを要求します。 それの最初の部分はあなたを助ける必要があります。

第三版リンクする

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top