package estructuras; import java.util.StringTokenizer; /** *
Title: Arboles de expresiones
*Description: Construye arboles de expresiones y los evalua
*Copyright: Copyright (c) 2006
*Company: UMSNH
* @author Dr. Felix Calderon Solorio * @version 1.0 */ public class Arbol_Expresion { Nodo raiz; /** * Constructor del Arbol de expresiones */ public Arbol_Expresion() { raiz = null; } /** * Calcula la profundidad de cada nodo en un arbol */ public void calculaHt() { calculaHt(raiz); } /** * Calcula la profundidad de cada nodo en un arbol * @param n Nodo */ public void calculaHt(Nodo n) { Nodo c; int i; n.ht = 0; //System.out.println(n.elemento[0] + " " + c); for(i=0; i<2; i++) { c = n.hijo[i]; if(c != null) { calculaHt(c); if(c.ht >= n.ht) n.ht = 1 + c.ht; } } } /** * Dada una cadena crea el arbol de expresion utilizando un pila * @param cadena String */ public boolean Crea(String cadena) { Stack P = new Stack(); StringTokenizer st; String dato; double sol; Nodo a, b; st = new StringTokenizer(cadena, " ", true); if (st.countTokens() != 0) { st = new StringTokenizer(cadena); while (st.hasMoreTokens()) { dato = st.nextToken(); if (dato.equals("+")) { a = (Nodo) P.pop(); b = (Nodo) P.pop(); P.push(new Nodo(new Character('+'), b, a)); } else { if (dato.equals("-")) { a = (Nodo) P.pop(); b = (Nodo) P.pop(); P.push(new Nodo(new Character('-'), b, a)); } else { if (dato.equals("*")) { a = (Nodo) P.pop(); b = (Nodo) P.pop(); P.push(new Nodo(new Character('*'), b, a)); } else { if (dato.equals("/")) { a = (Nodo) P.pop(); b = (Nodo) P.pop(); P.push(new Nodo(new Character('/'), b, a)); } else P.push(new Nodo(new Double(valor(dato)), null, null)); } } } } } this.raiz = (Nodo) P.pop(); if (P.isEmpty()) { System.out.println("Arbol construido correctamente"); return true; } else { System.out.println("No puede evaluarse " + cadena); return false; } } /** * Evalua un arbol creado * @return double */ public double evalua() { if(raiz != null) return eval(raiz); else return 0; } /** * Evalua en forma recursiva un arbol de expresiones * @param n Nodo * @return double */ private double eval(Nodo n) { double val1, val2; if (n.elemento[0] instanceof Double)return valor(n.elemento[0].toString()); else { val1 = eval(n.hijo[0]); val2 = eval(n.hijo[1]); switch (n.elemento[0].toString().charAt(0)) { case '+': return val1 + val2; case '-': return val1 - val2; case '*': return val1 * val2; case '/': return val1 / val2; default : return 0; } } } /** * Imprime el arbol de expresiones en diferentes ordenes * @param a char si a = p el recorrido es en preorden * si a = o, el recorrido es en orden y * si a = q, el recorrido es en postorden */ public void imprime(char a) { switch (a) { case 'p': preorden(raiz); break; case 'o': orden(raiz); break; case 'q': postorden(raiz); break; default : ordenes(raiz); } } /** * Recorrido en orden de un arbol * @param a Nodo */ public void orden(Nodo a) { if (a != null) { orden(a.hijo[0]); a.imprime(); orden(a.hijo[1]); } } public String orden() { return(orden(raiz, 0)); } public String orden(Nodo a, int h) { if (a != null) { return (orden(a.hijo[0], h+1) + espacios(h) + "(" + h + ") " + a.elemento[0] + "\n" + orden(a.hijo[1], h+1)); } return (""); } public String espacios(int n) { int i; String res = ""; for (i = 0; i < n; i++) res += " "; return res; } /** * Imprime el arbol en orden agregando parentesis para clarificar * la expresion evaluada en infijo. * @param a Nodo */ public void ordenes(Nodo a) { if (a != null) { if(tiene_hijos(a.hijo[0])) System.out.print("("); ordenes(a.hijo[0]); if(tiene_hijos(a.hijo[0])) System.out.print(")"); System.out.print(a.elemento[0]); if(tiene_hijos(a.hijo[1])) System.out.print("("); ordenes(a.hijo[1]); if(tiene_hijos(a.hijo[1])) System.out.print(")"); } } /** * Imprime la expresion correspondiente al subarbol dado * por el Nodo a * @param a Nodo * @return String */ public String expresion(Nodo a) { if (a != null) { return( (String) (tiene_hijos(a.hijo[0]) ? "(" : "") + expresion(a.hijo[0]) + (String) (tiene_hijos(a.hijo[0]) ? ")" : "") + a.elemento[0] + (String) (tiene_hijos(a.hijo[1]) ? "(" : "") + expresion(a.hijo[1]) + (String) (tiene_hijos(a.hijo[1]) ? ")" : "") ); } else return ""; } /** * Verifica que la funcion tenga hijos * @param a Nodo * @return boolean */ public boolean tiene_hijos(Nodo a) { if(a == null) return false; if (a.hijo[0] == null || a.hijo[1] == null) return false; else return true; } /** * Recorrido en preorden * @param a Nodo */ public void preorden(Nodo a) { if (a != null) { a.imprime(); preorden(a.hijo[0]); preorden(a.hijo[1]); } } /** * Recorrido en postorden * @param a Nodo */ public void postorden(Nodo a) { if (a != null) { postorden(a.hijo[0]); postorden(a.hijo[1]); a.imprime(); } } /** * Calcula el valor de una cadena de texto * @param x String * @return double */ public static double valor(String x) { return (Double.valueOf(x).doubleValue()); } /** * Programa principal con ejemplos * @param args String[] */ public static void main(String[] args) { Arbol_Expresion arbol = new Arbol_Expresion(); //arbol.Crea("5 9 2 * - 10 + 5 /"); arbol.Crea("7 10 + 2 / 4 3 * + 5 1 - / 9 +"); arbol.imprime(' '); System.out.println(" = " + arbol.evalua()); arbol.calculaHt(); arbol.imprime('q'); } }