albero di espressioni aritmetiche usando il linguaggio c

binary-tree c expression-trees

Domanda

Devo capire come creare un albero di espressioni aritmetiche.

Posso creare un albero binario semplice usando solo serie di numeri. C'è un esempio di codice qui sotto:

Questo è un nodo semplice che per il mio albero.

typedef struct _node {
    int key;
    struct _node *left, *right;
} node;

Ecco come aggiungo un nuovo nodo al mio albero binario:

node* add_tree(node *root, int val) {    
    if(NULL == root) {
        root = crnode(val);
    }    
    if (val < root->key) {
        if (NULL == root->left) {
            root->left = crnode(val);
        }
        else {
            add_tree(root->left, val);
        }
    }

    if (val > root->key) {
        if (NULL == root->right) {
            root->right = crnode(val);
        }
        else {
            add_tree(root->right, val);
        }
    }    
    return root;
}

Questa è la funzione principale e spiega come aggiungere un nuovo numero all'albero:

int main(int argc, const char * argv[])
    {    
        node *tree = add_tree(NULL, 5);
        tree = add_tree(tree, 6);
        tree = add_tree(tree, 7);
        tree = add_tree(tree, 3);
        return 0;
    }

La mia domanda è: come trasformare questo codice che posso usare non solo un numero ma un operatore (es. + - / *).

Per esempio ho bisogno di trasformare un'espressione 5 * (10 - 5) + 6 * 4 nell'albero. Come posso farcela?

Risposta accettata

Un nodo nell'espressione è una delle due cose: un operatore o un valore. Quindi devi delineare. Ci sono diversi modi per farlo, ma dato che sono compiti a casa, sono incline ad essere un po 'cauto e ti permettono di lavorare su qualcosa usando i concetti di programmazione che hai imparato fino ad ora.

Così ho deciso di aiutarti mostrandoti come sarebbe il tuo albero se avessi i tuoi nodi in funzione:

      +
     / \
    /   \
   /     \
  *       *
 / \     / \
5   -   6   4
   / \
  10  5

Potresti voler abbandonare la nozione di 'costruire un albero', e invece considerarlo come 'costruire un'espressione'. Potrebbe essere quello che ti trattiene. Si potrebbe finire con alcune funzioni che vengono utilizzate in questo modo:

node *expr = subtract(value(10), value(5));

Questo costruisce una parte dell'albero. Vedi cosa sta succedendo? =)



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é