Calculadora em Notação Polonesa Reversa usando Árvore Binária de Busca

Mais uma vez venho recorrer ao GUJ, parece que programação não é meu forte mesmo…

Bom, já consegui fazer algumas classes e aproveitar outras de alguns exercícios que fiz antes, mas o que preciso fazer agora e não consegui é um calculadora em notação polonesa reversa que armazena os operadores e operandos em uma árvore binária de busca. Os operadores (+, -, /, *) são os nodos e os operandos (5, 7, 12, 8) são as folhas.

Já fiz uma calculadora RPN que le uma string, tokeniza e executa a operação e também ja implementei uma árvore para armazenar os operadores e operandos, mas ela só aceita inteiros. Alguém tem um idéia de como fazer a leitura dos operadores e operandos, colocar eles na árvore corretamente e depois passar como string para que minha classe calculadora faça a operação? Já tentei tudo que foi gambiarra e nada funcionou.

Agradeço desde já! :smiley:

//CALCULADORA EM NOTAÇÃO POLONESA REVERSA USANDO PILHA

import java.util.Stack;
import java.util.StringTokenizer;

public class NPR{
	
	public NPR() {
		
	}
	
	public void executarOperacao(String s){
		//System.out.println("Calculando RPN");
		StringTokenizer st = new StringTokenizer(s);
		Stack pilha = new Stack();
		
		while(st.hasMoreTokens()){
			String token = st.nextToken();
		
			try{
				pilha.push(new Integer(token));
				System.out.println("Operando encontrado: " + token);
			}
			catch(NumberFormatException e){
				int operando1, operando2;
				switch(token.charAt(0)){
				case '*':
					operando2 = ((Integer)pilha.pop()).intValue();
					operando1 = ((Integer)pilha.pop()).intValue();
					System.out.println("Multiplicação: " + operando1 + " * " + operando2 + " = " + (operando1 * operando2));
					pilha.push(new Integer (operando1 * operando2));
					break;
				case '+':
					operando2 = ((Integer)pilha.pop()).intValue();
					operando1 = ((Integer)pilha.pop()).intValue();
					System.out.println("Adição: " + operando1 + " + " + operando2 + " = " + (operando1 + operando2));
					pilha.push(new Integer (operando1 + operando2));
					break;	
				case '-':
					operando2 = ((Integer)pilha.pop()).intValue();
					operando1 = ((Integer)pilha.pop()).intValue();
					System.out.println("Subtração: " + operando1 + " - " + operando2 + " = " + (operando1 - operando2));
					pilha.push(new Integer (operando1 - operando2));
					break;
				case '/':
					operando2 = ((Integer)pilha.pop()).intValue();
					operando1 = ((Integer)pilha.pop()).intValue();
					System.out.println("Divisão: " + operando1 + " / " + operando2 + " = " + (operando1 / operando2));
					pilha.push(new Integer (operando1/operando2));
					break;
				default:
					System.out.println("Erro na NPR!");
				}
			}
		}
	}
}
//NODO DA ÁRVORE

public class BSTNode {
protected int key;
protected BSTNode left, right;

	public BSTNode()
	{
		left = right = null;
	}

	public BSTNode(int num)
	{
		this(num,null,null);
	}

	public BSTNode(int num, BSTNode lt, BSTNode rt)
	{
		this.key = num; left = lt; right = rt;
	}   

	public int getKey()
	{
		return key;
	}

	public void setKey(int key) 
	{
		this.key = key;
	}

	public BSTNode getLeft()
	{
		return left;
	}

	public void setLeft(BSTNode left) 
	{
		this.left = left;
	}

	public BSTNode getRight()
	{
		return right;
	}

	public void setRight(BSTNode right)
	{
		this.right = right;
	}   
}
//ÁRVORE BINÁRIA DE PESQUISA

public class BST {
private BSTNode root = null;
private int cX = 0;

	public BST()
	{
	}
	
	public void clear() 
	{
		root = null;
	}
	
	public boolean isEmpty() 
	{
		return root == null;
	}
	
	public BSTNode getRootNode ()
	{
		return root;
	}
	
//-------------------------------------------------------
//Procurar
	
	public BSTNode search (int el)
	{
		return search(root,el);
	}
	
	private BSTNode search (BSTNode p, int el) 
	{
		while (p != null) 
		{
			/* se valor procuradp == chave do nó, retorna referência ao nó */ 
			if (el==p.key) return p;
			/* se valor procurado < chave do nó, procurar na sub-árvore esquerda deste nó */
			else if (el<p.key) p = p.left;
			/* se valor procurado > chave do nó, procurar na sub-árvore direita deste nó */
			else p = p.right;
		}
		// caso chave não foi achada, retorna null
		return null;
	}    

//-------------------------------------------------------
//Inserir	
	
	public boolean insert (int el)
	{
		BSTNode p = root, prev = null;
		// caso o valor já exista na árvore, não inserir e retornar false
		if (search(el)!=null) return false;
			// procurando um lugar para colocar o novo nó
			while (p != null)
			{  
				prev = p;
				if (el<p.key) p = p.left;
				else p = p.right;             
			}
			// se árvore vazia
			if (root == null)  root = new BSTNode(el);
			else if (prev.key<el) prev.right = new BSTNode(el);
			else prev.left = new BSTNode(el);
			return true;
	}
	
//-------------------------------------------------------
//Percorrer in-order
	
	public void inorder() 
	{
		inorder(root);
	}
	
		private void inorder (BSTNode p)
		{
			if (p != null) {
				inorder(p.left);
				System.out.print(p.key + " ");
				inorder(p.right);
			}
		}
//-------------------------------------------------------
//Percorrer preorder		
		
		public void preorder()
		{
			preorder(root);
		}
		
		private void preorder(BSTNode p) 
		{
			if (p != null) 
			{
				System.out.print(p.key + " ");
				preorder(p.left);
				preorder(p.right);
			}
		}

	
//-------------------------------------------------------
//Percorrer postorder
		
		public void postorder()
		{
			postorder(root);
		}
		
		private void postorder(BSTNode p) 
		{
			if (p != null) 
			{
				postorder(p.left);
				postorder(p.right);
				System.out.print(p.key + " ");
			}
		}



//-------------------------------------------------------
//Nó que retorna referência ao nó pai de uma chave
		
		protected BSTNode searchFather (int el) 
		{
			BSTNode p = root;
			BSTNode prev = null;
			// acha o nó p com a chave el
			while (p != null && !(p.key==el)) 
			{
				prev = p;      
				if (p.key<el)
					p = p.right;
				else p = p.left;
			}
			if (p!=null && p.key==el) 
				return prev;
			return null;
		}
		
//------------------------------------------------------------------------		
//Contar nós (in-order)
		public void countNodes() 
		{
			System.out.println("\nTotal de Nodos: " + countNodes(root));
		}
		
		public int countNodes(BSTNode p) 
		{  
			int count = 0;  
			if (p != null) {  
				count += countNodes(p.left);  
				count += 1;  // nó atual
				//System.out.print(p.key + " ");
				count += countNodes(p.right);
				//System.out.println("(" + count + ")");
			}  
			return count;  
		} 
		
//------------------------------------------------------------------------		
//Contar folhas da árvore
		public void countLeafNodes()
		{
			System.out.println("Folhas: " + countLeafNodes(root));
		}
		
		private int countLeafNodes(BSTNode p) 
		{
			if (p != null) 
			{		
				countLeafNodes(p.left);
				countLeafNodes(p.right);
				if (p.left == null && p.right == null){
					cX++;
					//System.out.println("FOLHA");
				}
				return cX;
			}
			return 0;
		}

		//----------------------------------------------------------------
		//verifica a altura de uma árvore binária.

		public void height()
		{
			System.out.println("Altura da árvore: " + height(root));
		}
				
		public int height(BSTNode no) {
			if (no == null)
				return 0;
			else {
				int heightLeft = height(no.getLeft());
				int heightRight = height(no.getRight());
				if (heightLeft > heightRight)
					return (heightLeft + 1);
				else
					return (heightRight + 1);
			}	
	    }

		//----------------------------------------------------------------
		//verifica se a árvore está cheia
		public boolean isFull(){
			int totalDeNodos = this.countNodes(root);
			int alturaDaArvore = this.height(root);
			//System.out.println("calc===" + (Math.pow(2, alturaDaArvore)-1));
			if(totalDeNodos == (Math.pow(2, alturaDaArvore)-1))
			{
				return true;
			}
			else return false;
		}
		
		
		//-------------------------------------------------------	
		//Remoção por cópia
	
		public void deleteByCopying (int el) 
		{
			BSTNode node, father = null;
			node = search (el) ; // procura nó a ser deletado
			if (node != null && node.key==el) 
			{
				if (node!=root) father = searchFather (el);  // procura pai do nó a ser deletado
				if (node.right == null)
				{             // nó não tem filho direito (caso 2 ou caso 1);
					if (node==root) root= node.left;
					else if (father.left == node) father.left = node.left;
					else father.right = node.left;
				}
				else if (node.left == null)
				{         // nó não tem filho esquerdo (caso 2)
					if (node==root) root= node.right;
					else if (father.left == node) father.left = node.right;
					else father.right = node.right;
				}
				else 
				{     // nó tem ambos os filhos: fazer remoção por cópia
					BSTNode tmp = node.left;     // 1. pegando sub-arvore esquerda
					while (tmp.right != null)        // 2. acha a posição mais a direita da sub-árvore esquerda do nó
						tmp = tmp.right;           
					deleteByCopying (tmp.key);     // remove por copia o nó que possui o maior  valor 
					// da sub-arvore esquerda do nó a ser deletado
					node.key = tmp.key;             // copia o valor da chave do maior nó da subárvore esquerda
				}
			}    
		else if (root != null)
			System.out.println("el " + el + " is not in the tree");
		else System.out.println("the tree is empty");
		}

		//-------------------------------------------------------
		//Remoção por fusão	

		public void deleteByMerging (int el)
		{
			BSTNode tmp, node,father = null;
			node = search (el) ; // procura nó a ser deletado
			if (node != null && node.key==el) 
			{
				if (node!=root) father = searchFather (el);  // procura pai do nó a ser deletado
				if (node.right == null)
				{     // nó não tem filho direito (caso 2);
					if (root==node) root=node.left;
					else if (father.left == node) father.left = node.left;
					else father.right = node.left;
				}
				else if (node.left == null) 
				{  // nó não tem filho esquerdo (caso 2)
					if (root==node) root=node.right;
					else if (father.left == node) father.left = node.right;
					else father.right = node.right;
				}
				else
				{  // se tem dois filhos, faz deleção por fusão                  
					tmp = node.left;                                     // pega sub-arvore esquerda
					while (tmp.right != null) tmp = tmp.right; //  pega filho mais a direita da sub-arvore esquerda     
					tmp.right = node.right;                      // o filho mais a direita da sub-arvore esquerda passa a ter
					// como filho direito o filho direito do nó a ser deletado
					if (root==node) root = node.left; 
					else if (father.left == node) father.left = node.left;                      
					else father.right = node.left;
				}            
			}
			else if (root != null) System.out.println("el " + el + " is not in the tree");
			else System.out.println("the tree is empty");
		}
}

Cara…Achei q eu era pinado… hauahuahuh…