Création d'un arbre d'expression

Question

Je souhaite créer un arbre d'expression pour pouvoir ensuite l'évaluer en utilisant les propriétés d'un arbre. Cependant, je ne sais pas vraiment par où commencer avec la création d'un arbre d'expression. Plus précisément, j'ai du mal à comprendre comment d'avoir deux types de variables dans l'arbre:

• Double (pour les nombres)
• char (pour les opérateurs)

Je cette LinkedBinaryTree classe:

public class LinkedBinaryTree<E> extends AbstractBinaryTree<E>{ 
protected static class Node<E> implements Position<E> { 
    private E element; // an element stored at this node 
    private Node<E> parent; // a reference to the parent node (if any) 
    private Node<E> left; // a reference to the left child (if any) 
    private Node<E> right; // a reference to the right child (if any) 

    public Node(E e, Node<E> above, Node<E> leftChild, Node<E> rightChild) { 
     element = e; 
     parent = above; 
     left = leftChild; 
     right = rightChild; 
    } 
    // accessor methods 
    public E getElement() { return element; } 
    public Node<E> getParent() { return parent; } 
    public Node<E> getLeft() { return left; } 
    public Node<E> getRight() { return right; } 
    // update methods 
    public void setElement(E e) { element = e; } 
    public void setParent(Node<E> parentNode) { parent = parentNode; } 
    public void setLeft(Node<E> leftChild) { left = leftChild; } 
    public void setRight(Node<E> rightChild) { right = rightChild; } 
} //----------- end of nested Node class ----------- 


protected Node<E> createNode(E e, Node<E> parent, 
     Node<E> left, Node<E> right) { 
    return new Node<E>(e, parent, left, right); 
} 

// LinkedBinaryTree instance variables 
protected Node<E> root = null; // root of the tree 
private int size = 0; // number of nodes in the tree 

// constructor 
public LinkedBinaryTree() { } // constructs an empty binary tree 

// nonpublic utility 

protected Node<E> validate(Position<E> p) throws IllegalArgumentException { 
    if (!(p instanceof Node)) 
     throw new IllegalArgumentException("Not valid position type"); 
    Node<E> node = (Node<E>) p; // safe cast 
    if (node.getParent() == node) // our convention for defunct node 
     throw new IllegalArgumentException("p is no longer in the tree"); 
    return node; 
} 

// accessor methods (not already implemented in AbstractBinaryTree) 

public int size() { 
    return size; 
} 


public Position<E> root() { 
    return root; 
} 


public Position<E> parent(Position<E> p) throws IllegalArgumentException { 
    Node<E> node = validate(p); 
    return node.getParent(); 
} 


public Position<E> left(Position<E> p) throws IllegalArgumentException { 
    Node<E> node = validate(p); 
    return node.getLeft(); 
} 


public Position<E> right(Position<E> p) throws IllegalArgumentException { 
    Node<E> node = validate(p); 
    return node.getRight(); 
} 

public Position<E> addRoot(E e) throws IllegalStateException { 
    if (!isEmpty()) throw new IllegalStateException("Tree is not empty"); 
    root = createNode(e, null, null, null); 
    size = 1; 
    return root; 
} 


public Position<E> addLeft(Position<E> p, E e) 
     throws IllegalArgumentException { 
    Node<E> parent = validate(p); 
    if (parent.getLeft() != null) 
     throw new IllegalArgumentException("p already has a left child"); 
    Node<E> child = createNode(e, parent, null, null); 
    parent.setLeft(child); 
    size++; 
    return child; 
} 

public Position<E> addRight(Position<E> p, E e) 
     throws IllegalArgumentException { 
    Node<E> parent = validate(p); 
    if (parent.getRight() != null) 
     throw new IllegalArgumentException("p already has a right child"); 
    Node<E> child = createNode(e, parent, null, null); 
    parent.setRight(child); 
    size++; 
    return child; 
} 


public E set(Position<E> p, E e) throws IllegalArgumentException { 
    Node<E> node = validate(p); 
    E temp = node.getElement(); 
    node.setElement(e); 
    return temp; 
} 

public void attach(Position<E> p, LinkedBinaryTree<E> t1, 
     LinkedBinaryTree<E> t2) throws IllegalArgumentException { 
    Node<E> node = validate(p); 
    if (isInternal(p)) throw new IllegalArgumentException("p must be a leaf"); 
    size += t1.size() + t2.size(); 
    if (!t1.isEmpty()) { // attach t1 as left subtree of node 
     t1.root.setParent(node); 
     node.setLeft(t1.root); 
     t1.root = null; 
     t1.size = 0; 
    } 
    if (!t2.isEmpty()) { // attach t2 as right subtree of node 
     t2.root.setParent(node); 
     node.setRight(t2.root); 
     t2.root = null; 
     t2.size = 0; 
    } 
} 

public E remove(Position<E> p) throws IllegalArgumentException { 
    Node<E> node = validate(p); 
    if (numChildren(p) == 2) 
     throw new IllegalArgumentException("p has two children"); 
    Node<E> child = (node.getLeft() != null ? node.getLeft() : node.getRight()); 
    if (child != null) 
     child.setParent(node.getParent()); // child’s grandparent becomes its parent 
    if (node == root) 
     root = child; // child becomes root 
    else { 
     Node<E> parent = node.getParent(); 
     if (node == parent.getLeft()) 
      parent.setLeft(child); 
     else 
      parent.setRight(child); 
    } 
    size--; 
    E temp = node.getElement(); 
    node.setElement(null); // help garbage collection 
    node.setLeft(null); 
    node.setRight(null); 
    node.setParent(node); // our convention for defunct node 
    return temp; 
} 

public String toString(){ 
    String treeString = "("; 
    if(root != null){ 
     treeString += nodeString(root); 
    } 

    return treeString+")"; 
} 

private String nodeString(Node<E> node){ 
    String str = nodeToString(node); 
    if(node.getLeft()!=null){ 
     str += "("+ nodeString(node.getLeft()) + ")"; 
    } 

    if(node.getRight()!=null){ 
     str += "("+ nodeString(node.getRight()) + ")"; 
    } 

    return str; 
} 

private String nodeToString(Node<E> node){ 
    return "" + node.getElement(); 
} 

public static void main(String[] args) { 
    LinkedBinaryTree<Integer> tree = new LinkedBinaryTree<Integer>(); 
    Position<Integer> p; 
    Position<Integer> p1; 
    Position<Integer> p2; 
    p = tree.addRoot(5); 
    p1 = tree.addLeft(p, 3); 
    p2 = tree.addRight(p, 7); 
    tree.addLeft(p1, 1); 
    tree.addRight(p1, 4); 
    tree.addLeft(p2, 6); 
    tree.addRight(p2, 9); 
    System.out.println(tree.toString()); 
} 
} 

Toute aide à ce sujet serait grandement appréciée, merci.

Answer 1

Votre problème est que vous utilisez le même type générique E partout dans votre classe d'arbre. Et cela n'a tout simplement pas de sens étant donné que vous voulez avoir différents types de nœuds dans le même arbre.

Ou d'un autre point de vue: votre problème est qu'il ne peut y avoir aucun E qui fonctionne pour le caractère et le double! Malheureusement, cela signifie que vous devrez peut-être retravailler des portions plus importantes de votre code. Comment faire est-ce au-delà de ce que je peux vous offrir en ce moment, mais il ya beaucoup de points de départ, même sur ce site qui aidera - this, ou des extraits sur geeksforgeeks ou that thing.

Answer 2

Vous pouvez utiliser une arborescence String et enregistrer les caractères et les doubles en tant que chaînes. Mais moi-même, je n'aime pas cette solution, puisque vous devez renvoyer la chaîne en double/caractères partout où vous l'utilisez, et vous devez savoir si c'est un nombre ou un opérateur tout le temps. Je voudrais créer une expression de classe et l'arbre contient des objets d'expression LinkedBinaryTree<Expression>. Ensuite, vous pouvez avoir des classes héritant de l'expression. Vous pouvez créer une classe pour les numéros class NumberExpression extends Expression et une classe class OperatorExpression extends Expression. La foolowup dépend de ce que vous voulez utiliser pour l'arbre.