Evaluando arboles de expresiones

algorithm directed-acyclic-graphs expression-trees graph tree

Pregunta

El libro sobre algoritmo de Skiena contiene la siguiente pregunta:

1) Evaluar la expresión dada como árbol binario en tiempo O (n), dados n nodos.

2) Evaluar la expresión dada como DAG en tiempo O (n + m), dados n nodos y m bordes en DAG.

introduzca la descripción de la imagen aquí

Podría pensar en un camino para la primera pregunta:

evaluate(node) {
     if(node has children){
          left_val = evaluate(node->left);
          right_val = evaluate(node->right);

          // find operation symbol for node and use it as
          // val = left_val operation right_val

          return val;
     }
     else {
          return node_value;
     }
}

Ya que visitamos cada nodo una vez, tomará O (n) tiempo.

Ya que el libro no tiene soluciones, ¿alguien puede decir si esto es correcto?

También puede alguien sugerir una solución para la segunda pregunta.

Gracias.

Respuesta aceptada

La primera manera me parece bien.

Para el DAG, si puede modificar el árbol para agregar valores almacenados en caché a cada nodo, puede usar el mismo algoritmo con un pequeño ajuste para no repetir si un nodo operador tiene un valor almacenado en caché. Este debe ser O (n + m) tiempo (como máximo una operación aritmética por nodo y como máximo una búsqueda de puntero por borde). Explícitamente:

evaluate(node) {
     if (node has value) {
          return node->value;
     } else {
          left = evaluate(node->left);
          right = evaluate(node->right);

          // find operation symbol for node and use it as
          // val = left_val operation right_val

          node->value = val;
          return val;
     }
}


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