Costruisci l'albero delle espressioni binarie

algorithm expression-trees

Domanda

Qualcuno potrebbe spiegare come costruire un albero di espressioni binarie.

Ad esempio, ho una stringa 2*(1+(2*1)); Come convertire questo in un albero di espressioni binarie.

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

Risposta popolare

Converti infisso in postfix o prefisso

L'input postfix è: ab + cde + **

  1. Considera il primo carattere se non è un simbolo, quindi crea il nodo aggiungilo allo stack
  2. Se il carattere è un simbolo, crea un nodo con elementi pop simbolo e aggiungi a sinistra ea destra del simbolo
  3. Spingere il nodo del simbolo nella pila.
  4. Ripeti 1, 2 e 3 fino a quando l'iteratore non ha più elementi

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

Maggiori informazioni: http://en.wikipedia.org/wiki/Binary_expression_tree



Autorizzato sotto: CC-BY-SA with attribution
Non affiliato con Stack Overflow
È legale questo KB? Sì, impara il perché
Autorizzato sotto: CC-BY-SA with attribution
Non affiliato con Stack Overflow
È legale questo KB? Sì, impara il perché