Buduj drzewo binarnej ekspresji

Question

Czy ktoś mógłby wyjaśnić, jak zbudować binarne drzewo wyrażeń.

Na przykład mam ciąg 2*(1+(2*1)); Jak przekonwertować to na binarne drzewo wyrażeń.

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

Answer 1

Konwersja wyrażenia na notację przedrostkową lub przyrostkową. Stamtąd powinno być całkiem proste. Algorytmy są wymienione w następujących linkach wiki.

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

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

Answer 2

trzeba będzie:

1. zdefiniować gramatyki, która opisuje język
2. napisać leksykalne analizatora, który odczytuje znaki z łańcucha
3. zapisu parser budujący drzewo z tokenów

na przykład spojrzeć na tego podejścia: http://en.wikipedia.org/wiki/Recursive_descent_parser

istnieją inne

Answer 3

Konwersja infix do postfix lub przedrostek

Wejście Postfix: ab + CDE + **

1. Rozważ pierwszy znak, jeśli nie jest symbolem, a następnie utwórz węzeł dodaj do stosu
2. Jeśli chara cter to symbol, a następnie utwórz węzeł z symbolami popowymi elementami i dodaj do lewej i prawej strony symbolu
3. Wciśnij symbol węzła na stosie.
4. Powtórz 1, 2 i 3 do iteratora nie ma więcej elementów Wdrożenie

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

Więcej informacji: http://en.wikipedia.org/wiki/Binary_expression_tree

Answer 4

To może być podzielony na dwa etapy:

1. Obliczyć priorytet dla każdego tokena.

   Na przykład: '+': 1, 'x',: 2, liczba INF, '(': dodanie 10 do podstawy, ')': odjąć 10 od podstawy)

2. budowy Cartesian tree oparciu priorytet przy użyciu stosu (około 5 linii kodu)

Możesz to zrobić w jednym skanie.