Albero parser o albero di espressione

c expression-trees parsing

Domanda

Sto facendo un calcolatore da riga di comando, quindi ho bisogno di analizzare le espressioni.

calc 2*(3+4)*5

Ho già fatto il passo dello scanner, restituendo un array di token. Ora sono al passaggio parser. Comunque non ho idea di come fare un parser / albero delle espressioni.

Questo è tutto ciò che ho finora:

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

Quindi passo l'array di token come:

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

Come puoi vedere il mio albero si solleva a sinistra. Non ho idea di come farlo funzionare ordinando da operatori in alto e numeri come foglie tra cui l'ordine di precedenza degli operatori.

Gradirei un'illuminazione, anche in termini di programmazione (codice).

Risposta popolare

Il tuo codice per la creazione di nodi mi sembra a posto. Il problema è che hai bisogno di codice per capire come costruire correttamente l'albero binario. Non puoi semplicemente attaccare un nodo ovunque trovi un puntatore NULL.

Espressione di esempio: 2*(3+4)*5

Si trasformerebbe in qualcosa di simile:

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

Il tuo insegnante dovrebbe darti un'idea su come farlo.

Quando ero al college, ho scritto questo tipo di codice, e abbiamo scritto il nostro "parser di discesa ricorsivo". Un altro approccio popolare sarebbe quello di utilizzare un sistema come GNU Bison.

Dovresti rivedere le tue note e vedere cosa l'insegnante ha detto a riguardo, e chiedi all'insegnante se davvero non lo sai.

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

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



Autorizzato sotto: CC-BY-SA with attribution
Non affiliato con Stack Overflow
È legale questo KB? Sì, impara il perché
Autorizzato sotto: CC-BY-SA with attribution
Non affiliato con Stack Overflow
È legale questo KB? Sì, impara il perché