Über Bäume und Präfix (Polnisch) Notation?

Question

Meine MIPS Assembly-Klasse muß mich in einem Ausdruck von unbekannter Größe in einen Parse-Baum zu lesen. Ich habe noch nie mit Bäumen zu tun, so ist dies, wie ich Werte ging um die Speicherung:

Der Benutzer kann sagen, trat der Ausdruck 1 + 3 bis 4 (jeder Operand nur eine Ziffer sein könnte 1-9)

Ihr am weitesten links stehende Kind-Knoten der Ausgangspunkt sein würde, und enthalten zwei Stücke von Daten

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

Dies ist, wie ich den Baum gebaut. Ich würde von Operanden Operator zum nächsten Operanden zum nächsten Operator Punkt, bis es keine mehr waren Werte in zu lesenden links.

Meine nächste Aufgabe war, den Baum rekursiv und gibt die Werte in Infix / prefix / Postfixnotation zu durchqueren.

Infix Traversal war kein Problem, zu überlegen, wie ich meinen Baum gebaut.

Ich bin auf dem Präfix fest. Erstens verstehe ich nicht voll es.

Wenn ich Ausgabe unser Ausdruck (1 + 3 - 4) in Präfix soll es kommen - + 1 3 4? Ich habe Probleme beim Anschluss an die Online-Beispiele.

Auch denken Sie, mein Baum richtig aufgebaut ist? Ich meine, habe ich keine Möglichkeit zu einem vorherigen Knoten aus dem aktuellen Knoten zu gehen, was bedeutet, ich muß immer Traversal von dem äußersten linken Kindknoten beginnen, die instinktiv nicht richtig selbst klingen, obwohl meine TA sagten, war der Weg zu gehen.

Vielen Dank für jede Hilfe.

Answer 1

Ihr Parse-Baum in etwa so aussehen sollte:

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

Jeder Knoten hat zwei Zeiger. Einer seiner linken Kind und ein zu seiner rechten Kind. Es besteht keine Notwendigkeit für Zeiger auf übergeordneten Knoten, wenn rekursive Traversal verwendet wird.

Hier ist ein Pseudo-Code:

Traversal für Infixschreibweise :

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

    print(node->value);

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

Traversal für Präfixnotation :

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

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

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

Traversal für Postfixnotation :

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

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

    print(node->value);
}

Sie würden die traverse Methode mit dem Wurzelknoten des Baumes nennen.

Ihre Node Datenstruktur müsse drei Mitglieder an:

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

Die Blätter des Baumes würde Null-Zeiger für leftChild und rightChild enthalten.

Manchmal hilft es, diese Dinge in einer höheren Sprache zu schreiben (was auch immer Sie sich wohl fühlen), um das Problem zu verstehen und zu „übersetzen“ auswählen Assembler dann. Ich erinnere mich, das Programmieren eines Blöcke Welt Simulation in MIPS-Assembler wie diese.

Answer 2

Generell sollte man einen Baum so konstruieren, dass alle Blattknoten (jene ohne Kinder) Operanden sind, und die internen Knoten (alles andere) sind die Betreiber. Dies sollte so sein, dass die Kinder von einem Operatorknoten seiner Operanden sind, oder selbst Operatoren, die Operanden haben. Wenn Sie einen Baum auf diese Weise konstruieren können, Formen, die verschiedenen Schreibweisen (Präfix, Postfix, Infix) sind ziemlich einfach - Sie folgen Sie einfach den Preorder, Postorder und inorder Querungen des Baumes, für die es gut bekannten Algorithmen

Soweit ich das beurteilen kann, sind Sie nicht einen Baum, sondern eine verknüpfte Liste der Konstruktion, und dies wird Ihnen nicht gut dienen. Sie haben zwei verschiedene Entitäten - Operanden und Operatoren - Sie haben sie anders zu behandeln

.

Answer 3

Ich bin damit einverstanden mit dem, was sykora sagt. Ich möchte hinzufügen, dass Sie auch einen Stapel in diesem Fall verwendet werden können. Wenn Ihre Aufgabe erfordert verwenden Sie speziell einen Baum, dann sykora Vorschlag würde am besten funktionieren. Allerdings könnte ein Stapel einfacher für einfache Ausdrucksauswertung zu programmieren.

Answer 4

Dies ist ein Beispiel für das allgemeine Problem der Compilierung, die ein gelöstes Problem. Wenn Sie eine Google auf Kompilieren Techniken tun, werden Sie alle Arten von Informationen in Bezug auf Ihr Problem erfahren.

Ihre Bibliothek sollte eine Kopie von Compiler: Prinzipien, Techniken und Werkzeuge von Aho, Sethi und Ullman. Wenn es es nicht hat, fordern sie für den Kauf (es ist das Standardwerk im Feld). Der erste Teil soll es Ihnen helfen.

Dritte Auflage Link