Ajuda em criar uma arvore de expressões

2 de dezembro de 2009 5 respostas

nellaf 2 de dezembro de 2009

Preciso de uma classe Arvore de expressões que converte expressões infix para postfix e infix para prefix, e já tenho estas classes:

public class Stack<E>{

     private int d = -1;
     private int MAX = 100;
     private int size = 0;
     private E[] stack;
     
     @SuppressWarnings("unchecked")
     public Stack(int size){
          stack = (E[])new Object[size];
          this.size = size;
     }
     
     public Stack(){
          this(MAX);
     }
     
     public void push(E o) throws OverflowStackException{
          if (size == (d+1))
               throw new OverflowStackException();
          
          d++;
          stack[d] = o;
     }
     
     public E top() throws EmptyException{
          if(d == -1)
               throw new EmptyException();
          return stack[d];
     }
     
     public E pop() throws EmptyException{
          if(d == -1)
               throw new EmptyException();
          d--;
          return stack[d+1];
     }
     
     public int size(){
          return d+1;
     }
     
     public boolean empty(){
          return d == -1;
     }
     
}

public class BTree<E>{
     
     E element;
     BTree<E> dir;
     BTree<E> esq;
    
     public BTree(){
          this(null);
     }
     
     public BTree(E x){
          elemento = x;
          esq = null;
          dir = null;
     }
     
     public BTree(E x, BTree<E> d,  BTree<E> e){
          elemento = x;
          dir = d;
          esq = e;
     }
     
     public E element() throws InvalidNode{
          if(this == null)
               throw new InvalidNode("Null node");
          return element;
     }
     
     public void setElement(E x){
          element = x;
     }
     
     public void setDir(BTree<E> d){
          dir = d;
     }
     
     public void setEsq(BTree<E> e){
          esq = e;
     }
     
     public BTree<E> getDir(){
          return dir;
     }
     
     public BTree<E> getEsq(){
          return esq;
     }

}

e agora preciso da classe mencionada e estou mesmo desesperado pois ainda consegui nada, alguém me ajude?
Sei que tenho que usar o String tokenizer e é só o que posso usar do java.util.

Desde já muito obrigado

5 Respostas

nellaf 3 de dez. de 2009

Alguém me pode ajudar??

nellaf 4 de dez. de 2009

Alguém me pode dizer onde está o erro:

import java.util.StringTokenizer;

public class ArvExp{
     
     private Stack<String> sinaisSt     ack;
     private Stack<BTree<String>> arvoreStack;
     private BTree<String> arvore;
     private StringTokenizer st;
     private String s;
     
     public ArvExp(String expressao) {
          
          st = new StringTokenizer(expressao," ");
          sinaisStack = new Stack<String>(expressao.length());
          arvoreStack = new Stack<BTree<String>>(expressao.length());
          
          while(st.hasMoreTokens()) {
               String caracter = "";
               s = st.nextToken();
               char[] car = s.toCharArray();
               for(int j = 0; j < car.length; j++){
                    if(Character.isDigit(car[j])) {
                         caracter = Character.toString(car[j]);   
                         BTree<String> t = new BTree<String>(caracter);
                         arvoreStack.push(t); 
                    }
                    else
                    {
                         if(!caracter.equals("(") && !caracter.equals(")")) {
                              while(!sinaisStack.empty() && !sinaisStack.top().equals("(")) {
                                   if(prioridade(caracter) <= prioridade(sinaisStack.top())){
                                        BTree<String> td = arvoreStack.pop();
                                        BTree<String> te = arvoreStack.pop();
                                        BTree<String> tt = new BTree<String>(sinaisStack.pop(), te, td); 
                                        arvoreStack.push(tt);}
                              }
                              sinaisStack.push(caracter);
                         } 
                         else if(caracter.equals("(")) 
                              sinaisStack.push(caracter);
                         
                         else if(caracter.equals(")")) {
                              while(!sinaisStack.top().equals("(")) {
                                   BTree<String> td = arvoreStack.pop();
                                   BTree<String> te = arvoreStack.pop();
                                   BTree<String> tt = new BTree<String>(sinaisStack.pop(), te, td);
                                   arvoreStack.push(tt);
                              }
                              sinaisStack.pop();
                              
                         }
                    }
               }
          }
          while(!sinaisStack.empty()) {
               BTree<String> td = arvoreStack.pop();
               BTree<String> te = arvoreStack.pop();
               BTree<String> tt = new BTree<String>(sinaisStack.pop(), te, td);
               arvoreStack.push(tt);
          }
          arvore = arvoreStack.pop();
     }
     
     private int prioridade(String s){
          
          if(s.equals("+") || s.equals("-"))
               return 1;
          else if(s.equals("*") || s.equals("/"))
               return 2;
          else
               return 3;
          
          
     }
     
     public BTree<String> getArvore(){
          return arvore;
     }
     
     public void getPos(){
          getPos(arvore);
     }
     
     public void getPos(BTree<String> n){
          if(n.getDir() != null)
               getPos(n.getDir());
          if(n.getEsq() != null)
               getPos(n.getEsq());
          System.out.print(n.element());
     }
     
     public void getPre(){
          getPre(arvore);
     }
     
     public void getPre(BTree<String> n){
          System.out.print(n.element());
          if(n.getDir() != null)
               getPre(n.getDir());
          if(n.getEsq() != null)
               getPre(n.getEsq());
          
     }
     
}

PS: Estou utilizando as 2 classes já anteriormente referenciadas:

Obrigado

nellaf 4 de dez. de 2009

Já encontrei o erro…
Mas será que podem ajudar agora em simplificar o construtor e/ou talvez reduzir alguns passos?

Muito obrigado

pablosaraiva 4 de dez. de 2009

Pelo que vi do seu código você implementou o algoritmo Shunting Yard.

Não está tão grande assim o código.

Está dando algum erro?

nellaf 4 de dez. de 2009

Já funciona mas queria simplicar mais se fosse possivel…

Criado 2 de dezembro de 2009

Ultima resposta 4 de dez. de 2009

Respostas 5

Participantes 2

5 Respostas

Topicos relacionados