構建二進制表達式樹

Question

有人可以解釋如何構建二進制表達式樹。

例如我有一個字符串2*(1+(2*1));如何將其轉換爲二進制表達式樹。

* 
| \ 
| \ 
2 + 
    |\ 
    1 * 
     |\ 
     2 1 

Answer 1

將表達式轉換爲前綴或後綴表示法。從那裏它應該是非常簡單的。算法在以下wiki鏈接中提到。

http://en.wikipedia.org/wiki/Polish_notation

http://en.wikipedia.org/wiki/Reverse_Polish_notation

Answer 2

你將需要：

1. 定義描述語言
2. 寫一個詞法分析器，從您的字符串
3. 寫入讀取的標記語法從令牌構建樹的解析器

例如，看看這個方法：http://en.wikipedia.org/wiki/Recursive_descent_parser

還有其他

Answer 3

轉換綴以後綴或前綴

後綴輸入爲：AB + CDE + **

1. 考慮第一個字符，如果它不是符號然後創建節點將它添加到堆棧
2. 如果字符cter是符號，然後使用符號彈出元素創建節點並將其添加到符號的左側和右側
3. 將符號節點插入到堆棧中。
4. 重複1，2和3，直到迭代器有沒有更多的元素

Java實現

public Tree.TreeNode createExpressionTree(){ 
    Iterator<Character>itr = postOrder.iterator(); 
    Tree tree = new Tree(); 
    NodeStack nodeStack = new NodeStack(); 
    Tree.TreeNode node; 
    while (itr.hasNext()) { 
     Character c = itr.next(); 
     if(!isDigit(c)){ 
      node = tree.createNode(c); 
      node.right = nodeStack.pop(); 
      node.left = nodeStack.pop(); 
      nodeStack.push(node); 
     }else{ 
      node = tree.creteNode(c); 
      nodeStack.push(node); 
     } 
    } 
    node = nodeStack.pop(); 
    return node; 
} 

更多信息：http://en.wikipedia.org/wiki/Binary_expression_tree

Answer 4

它可以分爲兩個步驟：

1. 計算每個令牌的優先級值。

   例如： '+'：1， 'X' 2，數：INF， '（'：添加10至基部， '）'：從基部減去10）的基礎上

2. 生成Cartesian tree優先使用堆棧（約5行代碼）

您可以在一次掃描中完成。