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á! 
//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");
}
}