aritmética expresión árbol usando lenguaje c

binary-tree c expression-trees

Pregunta

Necesito averiguar cómo crear un árbol de expresiones aritméticas.

Puedo crear un árbol binario simple usando solo un conjunto de números. Hay un ejemplo de código a continuación:

Este es un nodo simple que para mi árbol.

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

Así es como agrego un nuevo nodo a mi árbol 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;
}

Esta es la función principal y los pasos para agregar un nuevo número al árbol:

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

Mi pregunta es: cómo transformar este código que puedo usar no solo con un número sino con un operador (por ejemplo, + - / *).

Por ejemplo, necesito transformar una expresión 5 * (10 - 5) + 6 * 4 en árbol. ¿Cómo puedo hacerlo?

Respuesta aceptada

Un nodo en su expresión es una de dos cosas: un operador o un valor. Así que necesitas delinear. Hay varias maneras de hacer esto, pero ya que esta es la tarea, me inclino a ser un poco cauteloso y te permite resolver algo usando los conceptos de programación que has aprendido hasta ahora.

Así que decidí ayudarlo mostrando cómo se vería su árbol si tuviera sus nodos funcionando:

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

Es posible que desee eliminar la noción de "construir un árbol" y, en su lugar, pensar en "construir una expresión". Podría ser lo que te está frenando. Podría terminar con algunas funciones que se usan así:

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

Eso construye una parte del árbol. ¿Ves lo que está pasando? =)



Licencia bajo: CC-BY-SA with attribution
No afiliado con Stack Overflow
Licencia bajo: CC-BY-SA with attribution
No afiliado con Stack Overflow