Évaluation des arbres d'expression

algorithm directed-acyclic-graphs expression-trees graph tree

Question

Le livre de Skiena sur l'algorithme contient la question suivante:

1) Evaluez l'expression donnée sous forme d'arborescence binaire en temps O (n), à n nœuds.

2) Evaluez l'expression donnée sous forme de DAG dans O (n + m) time, à partir de n nœuds et de m arêtes dans DAG

entrez la description de l'image ici

Je pourrais penser à un moyen pour la première question:

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

Puisque nous visitons chaque nœud une fois, cela prendra O (n) temps.

Puisque le livre n’a pas de solution, est-ce que quelqu'un peut dire s'il le faut?

De plus, quelqu'un peut-il suggérer une solution pour la deuxième question.

Merci.

Réponse acceptée

La première façon me convient.

Pour le DAG, si vous pouvez modifier l'arborescence pour ajouter des valeurs en cache à chaque nœud, vous pouvez utiliser le même algorithme avec un petit ajustement pour ne pas renvoyer si un nœud d'opérateur a une valeur en cache. Il doit s'agir d'un temps O (n + m) (au plus une opération arithmétique par noeud et au plus une recherche de pointeur par bord). Explicitement:

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


Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow
Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow