9

Estou tentando montar uma Arvore Genérica em java para montar uma expressão booleana dentro de um algoritmo de expressão genética, essa árvore guardaria vários tipos de variáveis, não sei o certo qual a forma mais otimizada para se fazer isso, estava pensando em guardar operador lógicos como &&, || em strings e também os operadores matemáticos +, -, /, *. Os operadores seriam guardados nos nós dos galhos/raiz e os operandos que poderiam ser funções ou variáveis seriam guardados nos nós terminais(folhas), alguém tem alguma ideia? Passei o dia nesse problema e estou um pouco frustado.

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


}  

E a classe do nó.

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(", ");     

        }     
     }     
   }  

Ou seja, o que eu saberia implementar é bem simples, mas no projeto pessoal preciso implementar uma estrutura com essas características ou proximo das mesmas para chegar perto de alguma resultado satisfatório. Quem tiver a paciência para tentar ajudar, eu agradeço desde já.

8
  • Meu problema fica centrado no conceito, eu entendo como implementar uma árvore mas uma árvore que aceita esses variados tipos eu estou com duvidas. Vou postar mais ou menos o que eu sei. Commented 3/07/2014 às 21:21
  • Se eu entendi direito, o seu problema é que você quer apenas representar os operadores e operandos dentro de uma expressão lógica na forma de uma árvore (o fato de ser aplicado em um algoritmo genético não vem ao caso). Commented 3/07/2014 às 21:35
  • Isso Luiz, esse é meu maior impasse no momento. Commented 3/07/2014 às 21:37
  • 2
    @user2984406 Você tem experiência com tipos genéricos em Java? De qualquer forma, estou terminando de montar uma resposta com um exemplo.
    – mgibsonbr
    Commented 3/07/2014 às 21:41
  • 2
    @user2984406 Coloquei uma resposta com um exemplo prático de como tal árvore poderia ser modelada. Pela sua pergunta, vejo que já tem um bom domínio da estrutura de dados "árvore", então me concentrei em demonstrar como misturar nós de tipos diferentes numa mesma árvore (que parece ser o ponto central da sua dúvida). Os métodos para manipular, percorrer, etc, deixo por sua conta. :)
    – mgibsonbr
    Commented 3/07/2014 às 21:54

1 Resposta 1

12

Em primeiro lugar, se você precisa guardar tipos diferentes em uma estrutura de dados, você deve definir um supertipo para todos eles. Por exemplo, em vez do seu nó ser uma classe, faça com que ele seja uma interface genérica:

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

Então você pode definir seus nós de modo que eles implementem essa interface, porém cada um dando uma implementação ligeiramente diferente:

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

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

Para os operadores, minha sugestão é usar classes ou enumerações para representá-los (classes se você prevê que eles vão/podem mudar muito, enumerações se eles são mais ou menos fixos). Dessa forma você não só os representa, mas pode também fazer algo útil com eles:

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

(Nota: em vez de ter operadores unários e binários, fiz com que todos os operadores aceitassem um número variável de argumentos, para simplificar)

Por fim, você pode criar uma classe também genérica para representar os galhos/raiz:

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

Dessa forma, você pode montar a árvore que quiser:

// (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

Exemplo no ideone. Fonte do código para se criar um array genérico: essa resposta no SOen.

Esse é só um exemplo. Se achar necessário, pode criar mais tipos de folhas (até mesmo um tipo genérico Folha<T> com T valor), mais tipos de operadores (acho que nem faz sentido subtração com mais de 2 operandos), mais tipos de galhos, etc.

Nota: na minha resposta, omiti os construtores, modificadores e alguns tipos genéricos para o código não ficar muito extenso. O exemplo no ideone preenche as lacunas.

9
  • 2
    só uma duvida boba, esses 3 pontos seriam o que? O aplicar(I... operandos); ? Commented 3/07/2014 às 22:00
  • 2
    Eles permitem passar um número variável de argumentos pra função. Poderia também ser O aplicar(I[] operandos) - no final, o compilador vai transformar a função nisso.
    – mgibsonbr
    Commented 3/07/2014 às 22:02
  • Entendi, muito obrigado, você me deu uma grande ajuda :D Commented 3/07/2014 às 22:09
  • Estou conseguindo um erro Exception in thread "main" java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [Ljava.lang.Double; sabe o que pode estar acontecendo? está dando isso na hora de aplicar a soma. Commented 7/07/2014 às 20:01
  • 1
    @user2984406 É meio complicado: tipos genéricos em Java sofrem erasure quando são compilados (i.e. tudo vira Object no bytecode). Por isso, quando se cria um array com tipos paramétricos no código, ele vira um array de Object. Por outro lado, cada operador individual possui o tipo genérico definido em tempo de compilação. Por isso, ele espera um array de Double, e não de Object. Assim, quando ele tenta usar um Object[] onde se espera um Double[] dá um ClassCastException. Fazer um cast pra E[] não resolve, por causa do erasure. Não sei se ficou claro, mas espero ter ajudado.
    – mgibsonbr
    Commented 9/07/2014 às 23:07

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .