Parserbaum oder Ausdrucksbaum

c expression-trees parsing

Frage

Ich mache einen Befehlszeilenrechner, also muss ich Ausdrücke analysieren.

calc 2*(3+4)*5

Ich habe bereits den Scanner-Schritt gemacht und das Array eines Tokens zurückgegeben. Jetzt bin ich bei Parser Schritt. Ich habe jedoch keine Ahnung, wie man einen Parser / Ausdrucksbaum erstellt.

Das ist alles was ich bisher habe:

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

Dann überlasse ich das Token-Array wie folgt:

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

Wie du sehen kannst, richte ich meinen Baum einfach nach links. Ich habe keine Ahnung, wie es funktioniert, indem man die Operatoren an der Spitze und die Nummern als Blätter einschließlich der Reihenfolge der Operatoren sortiert.

Ich würde eine Erleuchtung schätzen, auch in der Programmierung (Code).

Beliebte Antwort

Ihr Code zum Erstellen von Knoten sieht für mich okay aus. Das Problem ist, dass Sie Code benötigen, um herauszufinden, wie Sie den Binärbaum richtig erstellen. Sie können einen Knoten nicht einfach überall dort festhalten, wo Sie einen NULL-Zeiger finden.

Ihr Beispielausdruck: 2*(3+4)*5

Würde zu etwas wie:

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

Ihr Lehrer hätte Ihnen eine Idee geben sollen, wie Sie dies tun können.

Als ich am College war, schrieb ich diese Art von Code und wir haben unseren eigenen "rekursiven Descent-Parser" geschrieben. Ein anderer beliebter Ansatz wäre ein System wie GNU Bison.

Sie sollten Ihre Notizen überprüfen und sehen, was der Lehrer dazu gesagt hat, und den Lehrer fragen, ob Sie es wirklich wissen.

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

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



Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Ist diese KB legal? Ja, lerne warum
Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Ist diese KB legal? Ja, lerne warum