評估表達式樹

Question

Skiena的書上算法包含了以下問題：

1）評估爲二叉樹O（n）的時間定表達式，給出n個節點。

2）在DAG中給定n個節點和m個邊緣的情況下，評估在O（n + m）時間中作爲DAG給出的表達式。

我能想到的第一個問題的方式：

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

由於我們訪問每個節點一次，它會採取O（n）的時間。

由於本書沒有解決方案，任何人都可以請告訴如果這是正確的？

也有人可以提出第二個問題的解決方案。

謝謝。

Answer 1

第一種方式對我來說很好看。

對於DAG，如果您可以修改樹以將緩存的值添加到每個節點，則可以使用相同的算法進行小的調整，以便在運算符節點具有緩存的值時不進行遞歸。這應該是O（n + m）時間（每個節點最多一次算術運算，每個邊最多一次指針查找）。明確地說：

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