從代數表達式創建二叉樹

我必須用Java創建算術評估器。爲此，我必須解析二叉樹中的代數表達式，然後計算並返回結果。因此，第一步如何解析二叉樹中的表達式？我知道這個理論，但我的概率是如何在Java中做到這一點。我讀了以下帖子 create recursive binary tree 從代數表達式創建二叉樹

但我錯過了基本的技巧或方法。我知道如何創建一個節點（我有一個類的方法，如returnNodeValue，isLeaf，isDoubleNode，isSingleNode等），但我想我需要一個方法在二叉樹中插入一個節點，以達到我想要的效果。有任何想法嗎？

來源

2011-10-23 Anila

你到目前爲止嘗試過什麼？僞代碼在那裏（並且網上有很多實現，無論好壞）。 –

我已經寫了函數來讀取後綴，中綴和前綴順序的樹。我知道有很多例子，但是我找不到我要找的東西。我需要從如何從代數表達式（我的意思是如何表達和測試優先級並存儲值等）開始創建一棵樹。我知道我要求的是基本的，但我只是卡住了。任何鏈接或幫助將不勝感激。謝謝。 – Anila

一般來說，要編寫一個解析器，你需要一個語法。然後有很多種解析器。在網上搜索「遞歸下降」解析器 - 很容易理解如何對它們進行編碼。順便問一下，這是功課嗎？ –

樹建設前綴表達式

def insert 

    Insert each token in the expression from left to right: 

    (0) If the tree is empty, the first token in the expression (must 
     be an operator) becomes the root 

    (1) Else if the last inserted token is an 
     operator, then insert the token as the left child of the last inserted 
     node. 

    (2) Else if the last inserted token is an operand, backtrack up the 
     tree starting from the last inserted node and find the first node with a NULL 
     right child, insert the token there. **Note**: don't insert into the last inserted 
     node. 
end def

讓我們做一個例子：+ 2 + 1 1

應用（0）。

適用（1）。

+ 
/
2

適用（2）。

+ 
/\ 
2 +

適用（1）。

+ 
/\ 
2 + 
/
    1

最後，申請（2）。

+ 
/\ 
2 + 
/\ 
    1 1

該算法對- */15 - 7 + 1 1 3 + 2 + 1 1

經過測試所以Tree.insert實現這三個規則。

insert(rootNode, token) 
    //create new node with token 
    if (isLastTokenOperator)//case 1 
     //insert into last inserted's left child 
    else {     //case 2 
     //backtrack: get node with NULL right child 
     //insert 
    } 
    //maintain state 
    lastInsertedNode = ?, isLastTokenOperator = ?

評估樹有點有趣，因爲你必須從樹的右下角開始。執行反向post-order遍歷。首先拜訪正確的孩子。

evalPostorder(node) 
    if (node == null) then return 0 
    int rightVal = evalPostorder(node.right) 
    int leftVal = evalPostorder(node.left) 
    if(isOperator(node.value)) 
     return rightVal <operator> leftVal  
    else 
     return node.value

鑑於從前綴表達式構建樹的簡單，我建議使用標準stack algorithm轉換從綴到前綴。在實踐中，您會使用堆棧算法來評估中綴表達式。

來源

2011-10-23 15:33:31 blackcompe

終於找到了感謝你的所有步驟。從中綴轉換爲前綴（參見[Shunting-yard算法]（https://en.wikipedia.org/wiki/Shunting-yard_algorithm）：比提供的鏈接更好地解釋） - >創建樹 - >使用反向後處理命令遍歷。謝謝！ – Fitz

_如果樹是空的，則表達式中的第一個標記（必須是是一個運算符）_除非整個表達式包含一個操作數。 – Fitz

我想你可能會有點困惑你應該做的：

...但我想我會需要一種方法在二叉樹中插入一個節點...

你所說的二叉樹實際上是一個分析樹，它不是嚴格的二叉樹（因爲不是所有的樹節點都是二叉樹）。（除了「二叉樹」有二進制搜索樹的內涵，這不是你在這裏需要的。）

你已經想通了解析表達式，解析樹的構造非常直-前鋒。例如：

Tree parseExpression() { 
    // .... 
    // binary expression case: 
     Tree left = parseExpression(); 
     // parse operator 
     Tree right = parseExpression(); 
     // lookahead to next operator 
     if (...) { 
     } else { 
      return new BinaryNode(operator, left, right); 
     } 
    // ... 
}

注：這是行不通的代碼...這是一個提示，以幫助你做你的功課。

來源

2011-10-23 14:39:02

從代數表達式創建二叉樹

回答

相關問題