Generic Tree, how to do?

Question

I’m trying to assemble a Generic Tree in java to assemble a Boolean expression within a gene expression algorithm, this tree would hold several types of variables, I’m not sure which is the most optimized way to do this, I was thinking of saving logical operator as &&, || in strings and also mathematical operators +, -, /, *. Operators would be stored at branch/root nodes and operands that could be functions or variables would be stored at terminal nodes (leaves), anyone have any idea? I spent the day in that trouble and I’m a little frustrated.

public class ArvoreJava {    
   public static No raiz; // o único campo de dado em Arvore    


   public ArvoreJava() { // construtor    
     raiz = null;  //nenhum nó na arvore    
   }   
public static No insere(String palavra, No no) {  //metodo insere  

        if(no == null){  
            no = new No(palavra);  //se nao existir nó cria um novo  
        }  

        else if((compare(palavra, no.palavra)) < 0){ // faz comparação, se palavra  
            no.filhoEsquerda = ArvoreJava.insere( palavra , no.filhoEsquerda);// menor que nó, insere na esquerda  
        }  
        else if((compare(palavra, no.palavra)) > 0){//se palavra maior que nó, insere na direita  
           no.filhoDireita = ArvoreJava.insere(no.palavra, no.filhoDireita);  
        }  
        else{// senão, palavra já contem  
            System.out.println("ERRO: valor já existe na árvore.");  
            return null;  
        }  

        return no;  

}  
public static void caminhando(ArvoreJava arv){//caminha na arvore   
                System.out.println("Pré-ordem: ");  
        arv.preordem(arv.raiz);  

}  
public static int compare(String palavra, String no){ // compara strings e retorna um inteiro  
     return palavra.toString().compareTo(no.toString());//-1 menor, 1 maior, 0 iguais  
}  


        public  void preordem(No no)    {//caminha em preordem  
            if (no == null){  
        return;  
        }  
    System.out.println(no.palavra);  
    preordem(no.filhoEsquerda);  
    preordem(no.filhoDireita);  
    }  


}  

And the class of the knot.

package arvore;  

public class No {  

     String palavra;    //dado  
     No filhoEsquerda; //cria filho  a esquerda  
     No filhoDireita;  // cria filho a direita  

    public No(String palavra){  
        this.palavra = palavra;  
    }  

     public void mostraNo(){     
       {     

             System.out.print(palavra);     
             System.out.print(", ");     

        }     
     }     
   }  

That is, what I would know how to implement is very simple, but in the personal project I need to implement a structure with these characteristics or close to them to get close to some satisfactory result. Whoever has the patience to try to help, I thank you in advance.

Answer 1

First, if you need to store different types in a data structure, you must define a supertype for all of them. For example, instead of your node being a class, make it a generic interface:

interface No<T> {
    T avaliar();
}

So you can define your nodes so that they implement this interface, but each one giving a slightly different implementation:

class FolhaNumerica implements No<Double> {
    double valor;
    Double avaliar() { return valor; }
}

class FolhaBooleana implements No<Boolean> {
    boolean valor;
    Boolean avaliar() { return valor; }
}

For operators, my suggestion is to use classes or enumerations to represent them (classes if you predict that they will/can change a lot, enumerations if they are more or less fixed). That way you not only represent them, but can also do something useful with them:

interface Operador<E,S> {
    S aplicar(E[] operandos);
    Class<E> obterClasseOperandos(); // Workaround para uma limitação nos tipos genéricos
}

class Soma implements Operador<Double,Double> {
    String toString() { return "+"; }
    Double aplicar(Double[] operandos) {
        double ret = 0;
        for ( Double d : operandos )
            ret += d;
        return ret;
    }
    Class<Double> obterClasseOperandos() { return Double.class; }
}

class Conjuncao implements Operador<Boolean,Boolean> {
    String toString() { return "&&"; }
    Boolean aplicar(Boolean[] operandos) {
        for ( Boolean b : operandos )
            if ( !b )
                return false;
        return true;
    }
    Class<Boolean> obterClasseOperandos() { return Boolean.class; }
}

class Igualdade implements Operador<Double,Boolean> {
    String toString() { return "=="; }
    Boolean aplicar(Double[] operandos) {
        double primeiro = operandos[0];
        for ( Double d : operandos )
            if ( d != primeiro )
                return false;
        return true;
    }
    Class<Double> obterClasseOperandos() { return Double.class; }
}

(Note: instead of having unary and binary operators, I made all operators accept a variable number of arguments, to simplify)

Finally, you can create a generic class to represent the branches/root:

class Galho<E,S> implements No<S> {
    Operador<E,S> op;
    No<E>[] operandos;

    S avaliar() {
        @SuppressWarnings("unchecked")
        E[] array = (E[])Array.newInstance(op.obterClasseOperandos(), operandos.length);
        for ( int i = 0 ; i < array.length ; i++ )
            array[i] = operandos[i].avaliar(); // Avalia cada sub-nó recursivamente

        return op.aplicar(array); // Passa os resultados para o operador
    }
}

That way, you can ride the tree you want:

// (4 == 2 + 2) && true
No<Double> mais = new Galho<Double,Double>(new Soma(), new FolhaNumerica(2), new FolhaNumerica(2))
No<Boolean> igual = new Galho<Double,Boolean>(new Igualdade(), new FolhaNumerica(4), mais);
No<Boolean> raiz = new Galho<Boolean,Boolean>(new Conjuncao(), igual, new FolhaBooleana(true));

boolean resultado = raiz.avaliar(); // true

Example in the ideone. Source code to create a generic array: that answer in Soen.

This is just an example. If you think it necessary, you can create more types of sheets (even a generic type Folha<T> with T valor), more types of operators (I don’t think subtraction with more than 2 operands makes sense), more types of branches, etc.

Note: in my reply, I omitted constructors, modifiers and some generic types for the code not to be too extensive. The example in ideone fills the gaps.