Frage

Skienas Buch über Algorithmus enthält folgende Frage:

1) Evaluiere den Ausdruck, der als binärer Baum in O (n) Zeit gegeben ist, mit n Knoten.

2) Evaluiere Ausdruck, der als DAG in O (n + m) -Zeit gegeben ist, gegeben durch n Knoten und m Kanten in DAG.

Bildbeschreibung hier eingeben

Ich könnte mir einen Weg für die erste Frage vorstellen:

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

Da wir jeden Knoten einmal besuchen, dauert es O (n) Zeit.

Da das Buch keine Lösungen hat, kann jemand bitte sagen, ob das stimmt?

Auch kann jemand eine Lösung für die zweite Frage vorschlagen.

Vielen Dank.

Akzeptierte Antwort

Der erste Weg sieht gut aus für mich.

Wenn Sie für die DAG die Struktur so ändern können, dass jedem Knoten zwischengespeicherte Werte hinzugefügt werden, können Sie denselben Algorithmus mit einer kleinen Optimierung verwenden, um nicht zu rekursiv zu machen, wenn ein Operatorknoten einen zwischengespeicherten Wert hat. Dies sollte O (n + m) Zeit sein (höchstens eine arithmetische Operation pro Knoten und höchstens eine Zeiger-Suche pro Kante). Ausdrücklich:

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


Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow