Atividade 04 - TAP II

package br.pucpr;

import java.util.*;
import br.pucpr.ed.NoAB;

/**
 * Algoritmo para gerar uma árvore binária para representar uma expressão
 * algébrica qualquer.
 *
 * @author s.luis
 */
public class GeradorArvore {

    private static Scanner input;

    public static void main(String[] args) throws Exception {
        input = new Scanner(System.in);
        String inFix;
        System.out.print("InFix: ");
        inFix = input.next();
        String postFix = infixToPostfix(inFix);
        System.out.println("PostFix: " + postFix);
        System.out.print("Árvore: ");
        montagemArvore(postFix);
    }

    /**
     * Verifica qual operador tem precedência na equação
     */
    public static boolean verificaPrecedencia(char op1, char op2) {
        int opp1 = -1, opp2 = -1;

        // Verifica qual o operador lido e atribui um valor para ele
        // Caso o operador seja + ou - o valor atribuido será 0
        // Caso o operador seja * ou / o valor atribuido será 1
        switch (op1) {
        case '+':
        case '-':
            opp1 = 0;
            break;
        case '*':
        case '/':
            opp1 = 1;
            break;
        }
        switch (op2) {
        case '+':
        case '-':
            opp2 = 0;
            break;
        case '*':
        case '/':
            opp2 = 1;
            break;
        }

        // Retorna verdadeiro caso o operador 1 seja maior que o operador 2
        return op1 > op2;
    }

    /**
     * Converte uma equação infix (notação de calculadora normal) para uma
     * equação postfix (notação de calculadora hp)
     */
    public static String infixToPostfix(String inFix) {
        String postFix = "";

        // Crie uma pilha vazia
        Stack<Character> pilhaEq = new Stack<Character>();

        // Leia o String Infix da esquerda para direita
        for (char aux : inFix.toCharArray()) {
            // Se o caracter for um abre parêntesis, adicione-o à pilha
            if (aux == '(')
                pilhaEq.push(aux);

            // Se o caracter é um operando
            if ((aux >= '0' && aux <= '9') || (aux >= 'a' && aux <= 'z'))
                // Adcione-o ao String PostFix
                postFix += aux;

            // Se o caracter for um operador
            if (aux == '+' || aux == '-' || aux == '*' || aux == '/') {
                // E a pilha não estiver vazia, compara a precedência do
                // caracter e do elemento do topo da pilha
                while (!pilhaEq.empty()
                        && (verificaPrecedencia(pilhaEq.peek(), aux))) {
                    // Se o elemento do topo da pilha for de maior precedência
                    // remova o elemento e adcione-o ao String
                    postFix += pilhaEq.pop();
                }
                // Adcione o caracter lido a pilha
                pilhaEq.push(aux);
            }
            // Se o caracter for um fecha parêntesis
            if (aux == ')') {
                // Leia os vários elementos da pilha até encontrar um abre
                // parêntesis
                while (pilhaEq.peek() != '(') {
                    // E adcione os elementos ao String postfix
                    postFix += pilhaEq.pop();
                }
                // Remova o abre parêntesis
                pilhaEq.pop();
            }
        }

        // Enquanto não esvaziar a pilha
        while (!pilhaEq.empty()) {
            // Remova todos os elementos passando para a String postfix
            postFix += pilhaEq.pop();
        }

        // Retorna a equação postfix
        return (postFix);
    }

    /**
     * Dada uma equação postfix, monta-se uma árvore binária
     */
    public static void montagemArvore(String postfix) throws Exception {
        // Crie uma pilha vazia
        Stack pilhaArv = new Stack();
        NoAB subArv = null;

        // Leia o string PostFix
        for (char ch : postfix.toCharArray()) {
            // Se o caracter lido for um operando
            if (ch >= '0' && ch <= '9')
                // Insira este caracter na pilha
                pilhaArv.push(ch);
            // Se o caracter lido for um operador
            if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
                // Crie uma nova sub-árvore que terá o operador como root
                subArv = new NoAB(ch);
                // E o primeiro elemento da pilha como filho direito
                subArv.adcionaDireita(pilhaArv.pop());
                // E o segundo elemento da pilha como filho esquerdo
                subArv.adcionaEsquerda(pilhaArv.pop());

                // Insira esta nova sub-árvore na pilha
                pilhaArv.push(subArv);
            }
        }

        // Imprime a árvore pelo método pós-ordem
        posOrdem(subArv);
    }

    public static void posOrdem(NoAB raiz) {
        // condição de parada
        if (raiz == null)
            return;
        // 1) percorrer sae
        posOrdem(raiz.getEsquerda());
        // 2) percorrer sad
        posOrdem(raiz.getDireita());
        // 3) tratar raiz
        System.out.print(raiz.getDado() + ", ");

    }

}