Build Binary Expression Tree

Könnte mir jemand erklären, wie man einen binären Ausdruck Baum.

Ich habe zum Beispiel einen string 2*(1+(2*1)); Wie zu konvertieren, das in einem binären Ausdruck Baum.

 *
 | \
 |  \
 2  +
    |\
    1 *
      |\
      2 1
Könnten Sie eine Lösung implementieren, mit der Rangier-yard-Algorithmus. Hier sind einige details auf wikipiedia: <en.wikipedia.org/wiki/Shunting-yard_algorithm>. Dieser algo erfunden wurde von Edsger Dijkstra, es ist eine sehr schöne alternative. Wenn Sie müssen einige details, kann ich nach einem code-Beispiel, das schrieb ich in C# vor einiger Zeit, aber ich nehme an, dass der wikipedia-link ist mehr als genug.

InformationsquelleAutor user1110839 | 2012-02-03

  1. 10

    Convert infix -, postfix-oder Präfix

    Postfix-Eingabe: a b + c d e +**

    1. Prüfen der ersten Zeichen wenn es kein symbol, dann erstellen Sie Knoten hinzufügen stack
    2. Ob-Charakter ist das symbol erstellen Sie dann den Knoten mit dem symbol pop-Elemente und fügen Sie Sie Links und rechts des symbols
    3. Push symbol Knoten in dem stack.
    4. Wiederholen Sie Schritt 1, 2 und 3 bis zu iterator keine weiteren Elemente mehr

    Java-Implementierung

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

    Mehr info: http://en.wikipedia.org/wiki/Binary_expression_tree

    Hier symbol = operator

    InformationsquelleAutor SHA

  2. 2

    müssen Sie:

    1. definieren Sie eine Grammatik, die beschreibt, Ihre Sprache
    2. schreiben Sie einen lexikalischen Analysator, der liest das Token aus Ihrem string
    3. schreiben Sie einen parser baut den Baum von der Token

    zum Beispiel, nehmen Sie einen Blick an diesem Ansatz: http://en.wikipedia.org/wiki/Recursive_descent_parser

    gibt es andere

    Dies ist wahrscheinlich overkill für was ist eine ziemlich einfache Aufgabe, um visuell zu zeigen, wie Ausdrücke interpretiert werden.

    InformationsquelleAutor akonsu

  3. 0

    Konvertieren der Ausdruck Präfix-oder postfix-notation. Von dort aus sollte es ziemlich einfach sein. Algorithmen sind im folgenden wiki-links.

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

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

    InformationsquelleAutor ElKamina

  4. 0

    Kann es gliedert sich in zwei Schritte:

    1. Berechnen priority-Wert für jedes token.

      Beispiel: '+': 1, 'x': 2, Nummer: inf, '(': add 10, base, ')': subtrahieren Sie 10 von der Basis)

    2. Bauen Kartesische Baum basierend auf Priorität unter Verwendung einer stack (ca 5 Zeilen code)

    Können Sie es tun in einem scan.

    InformationsquelleAutor Pei

Schreibe einen Kommentar