使用C++中的樹評估後綴表達式

我應該使用表達式樹來評估後綴表達式。假設我有這樣的使用C++中的樹評估後綴表達式

- 
/\ 
    + * 
/\/\ 
a b c d

我首先需要計算A + B子樹，並將其結果存儲在+節點，則c * d等，直到我有結果的根節點的一棵樹。

我嘗試了使用堆棧的遞歸方法，但那不起作用。的僞代碼看起來是這樣

函數eval（節點）
的eval（節點 - >左）
的eval（節點 - >右）
如果（節點是葉節點）推在堆棧上
else if（節點是操作數）從棧中彈出和彈出b node-> value = a-> op操作b->值 delete ab;

但是這沒有奏效。我還必須在每一步顯示樹，以顯示節點正在減少。我GOOGLE了很多次，但我無法找到所需的答案。任何人都請幫助我如何做到這一點。

void expression_tree::evaluate(node *temp) 
{ 
    if(!temp) 
    return; 
/// stack_postfix obj; 
    stack_postfix obj2; 
    evaluate(temp->left); 
    evaluate(temp->right); 
     if(temp->right == NULL && temp->left == NULL) 
     { 
      obj2.push(temp); 
     } 
     else 
     { 
      node * a = obj2.pop(); 
      node *b = obj2.pop(); 
      temp->value = a->value + b->value; 
      delete a; 
      delete b; 
     }

}

來源

2013-10-31 chaudrhy

究竟沒有工作？請顯示相關代碼並準確描述哪些方法無效。 –

您需要在步驟5中將結果值壓入堆棧 – Erbureth

遞歸方法不使用堆棧explicilty：它使用當您執行遞歸時自動獲取的激活幀堆棧。 – EJP

你有2個選擇：

eval of leaf：

1 - 只需推值疊放

EVAL non_leaf的：

1 - EVAL左， - 記住：EVAL結果加入到疊加。

2 - EVAL右，

3 - 彈出2項，

4 - 計算，

5 - 推結果。

末你必須在堆棧1項 - 最後的結果

編輯：

void expression_tree::evaluate(node *temp, stack& s) 
{ 
    if(!temp) 
     return; 

    if(temp->left != NULL && temp->right != NULL){ 
     //only 1 pointer is illegal! 
     evaluate(temp->left); 
     evaluate(temp->right); 
     node* n2 = s.pop(); 
     node* n1 = s.pop(); 
     //in the stack should be only leaves 
     temp->value = n1->value + n2->value;//use switch by operator 
     delete temp->left; 
     temp->left = NULL; 
     delete temp->right; 
     temp->right=NULL; 
    } 
    s.push (temp); 
}

來源

2013-10-31 10:03:32 SHR

您在其他部分忘記obj2.push(temp->balue);

不過，也有更多的失誤，堆棧需要在函數調用之間共享，這樣的功能其實可以處理它

來源

2013-10-31 09:48:42 Erbureth

我也嘗試了使用迭代方法的相同方法，但那也不適用於我。我只想知道我嘗試使用的方法是否正確。還有另一種方法來做到這一點？ – chaudrhy

您的基於堆棧的方法是正確的，除了一些細節和有點不明確的實現。 – Erbureth

使用C++中的樹評估後綴表達式

回答

相關問題