代数式からバイナリツリーを作成する

Question

Javaで算術演算子を作成する必要があります。これを行うには、私はバイナリツリーで代数式を解析し、その結果を計算して返す必要があります。だから最初のステップでは、私はどのようにバイナリツリーの式を解析することができますか？私は理論を知っているが、私の問題はJavaでそれをやる方法だ。私は次の記事を読む create recursive binary tree

しかし、私は基本的なトリックや方法がありません。私はノードを作成する方法を知っています（私はreturnNodeValue、isLeaf、isDoubleNode、isSingleNodeなどのメソッドを持つクラスを持っています）。しかし、私は、バイナリツリーにノードを挿入して、必要な情報を得るメソッドが必要です。何か案は？

Answer 1

接頭式のツリー構築

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 

このアルゴリズムは、そうTree.insert実装は、これらの3つのルールである- */15 - 7 + 1 1 3 + 2 + 1 1

に対してテストされています。

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を使用してお勧めしたいです。実際には、スタックアルゴリズムを使って中置式を評価します。

Answer 2

私はあなたがやっていることになっているかについて少し混乱するかもしれないと思う：

を...しかし、私は、バイナリツリーにノードを挿入する方法が必要だと思います...

あなたが話しているバイナリツリーは、実際には解析ツリーであり、厳密にはバイナリツリーではありません（すべてのツリーノードがバイナリではないため）。 （バイナリツリーにはバイナリの意味があります。検索ツリーです。

パーズツリーの構築はかなりストレートです - フォワード。例えば：

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); 
     } 
    // ... 
} 

---

注：このコードを動作していない...あなたがあなたの宿題を支援するためのヒントです。