Una forma sencilla y rápida de aprender JAVA, observando y deduciendo cómo se comporta el lenguaje a través de ejemplos prácticos.

viernes, 21 de septiembre de 2012

Conversión de Infijo a Postfijo usando pilas

Ver referencia: Infijo-Posfijo


Codigo:

//Conversión de notación Infija a Postfija mediante uso de pilas
package infixpostfix4;

import java.util.Scanner;
import java.util.Stack;

public class InfixPostfix4 {
  public static void main(String[] args) {

    //Entrada de datos
    System.out.println("*Escribe una expresión algebraica: ");
    Scanner leer = new Scanner(System.in);

    //Depurar la expresion algebraica
    String expr = depurar(leer.nextLine());
    String[] arrayInfix = expr.split(" ");

    //Declaración de las pilas
    Stack < String > E = new Stack < String > (); //Pila entrada
    Stack < String > P = new Stack < String > (); //Pila temporal para operadores
    Stack < String > S = new Stack < String > (); //Pila salida

    //Añadir la array a la Pila de entrada (E)
    for (int i = arrayInfix.length - 1; i >= 0; i--) {
      E.push(arrayInfix[i]);
    }

    try {
      //Algoritmo Infijo a Postfijo
      while (!E.isEmpty()) {
        switch (pref(E.peek())){
          case 1:
            P.push(E.pop());
            break;
          case 3:
          case 4:
            while(pref(P.peek()) >= pref(E.peek())) {
              S.push(P.pop());
            }
            P.push(E.pop());
            break; 
          case 2:
            while(!P.peek().equals("(")) {
              S.push(P.pop());
            }
            P.pop();
            E.pop();
            break; 
          default:
            S.push(E.pop()); 
        } 
      }

      //Eliminacion de `impurezas´ en la expresiones algebraicas
      String infix = expr.replace(" ", "");
      String postfix = S.toString().replaceAll("[\\]\\[,]", "");

      //Mostrar resultados:
      System.out.println("Expresion Infija: " + infix);
      System.out.println("Expresion Postfija: " + postfix);

    }catch(Exception ex){ 
      System.out.println("Error en la expresión algebraica");
      System.err.println(ex);
    }
  }

  //Depurar expresión algebraica
  private static String depurar(String s) {
    s = s.replaceAll("\\s+", ""); //Elimina espacios en blanco
    s = "(" + s + ")";
    String simbols = "+-*/()";
    String str = "";
 
    //Deja espacios entre operadores
    for (int i = 0; i < s.length(); i++) {
      if (simbols.contains("" + s.charAt(i))) {
        str += " " + s.charAt(i) + " ";
      }else str += s.charAt(i);
    }
    return str.replaceAll("\\s+", " ").trim();
  }

  //Jerarquia de los operadores
  private static int pref(String op) {
    int prf = 99;
    if (op.equals("^")) prf = 5;
    if (op.equals("*") || op.equals("/")) prf = 4;
    if (op.equals("+") || op.equals("-")) prf = 3;
    if (op.equals(")")) prf = 2;
    if (op.equals("(")) prf = 1;
    return prf;
  }
}


Resultado:

run:
*Escribe una expresión algebraica:
2*(23+6)-1
Expresion Infija: (2*(23+6)-1)
Expresion Postfija: 2 23 6 + * 1 -
BUILD SUCCESSFUL (total time: 4 seconds)

62 comentarios:

  1. Respuestas
    1. http://censorcosmico.blogspot.com.es/2012/09/evaluar-expresion-postfija-usando-pilas.html

      Eliminar
  2. gracias pero una pregunta como guardo postfix para evaluar con el metodo del link anterior?

    ResponderEliminar
    Respuestas
    1. Si lo que quieres es evaluar una expresión directamente dale al siguiente link:

      http://censorcosmico.blogspot.com.es/2012/06/obtener-el-resultado-numerico-de-una.html

      Eliminar
  3. Hola, quiero saber para qué pones este método? Gracias

    //Depurar expresión algebraica
    private static String depurar(String s) {
    s = s.replaceAll("\\s+", ""); //Elimina espacios en blanco
    s = "(" + s + ")";
    String simbols = "+-*/()";
    String str = "";

    //Deja espacios entre operadores
    for (int i = 0; i < s.length(); i++) {
    if (simbols.contains("" + s.charAt(i))) {
    str += " " + s.charAt(i) + " ";
    }else str += s.charAt(i);
    }
    return str.replaceAll("\\s+", " ").trim();
    }

    ResponderEliminar
    Respuestas
    1. Simplemente es para separar los números de los simbolos con un espacio.

      Ej:
      2*(23+6) -1
      lo convierte en:
      ( 2 * ( 23 + 6 ) - 1 )

      Y con ese nuevo formato queda lista para agregarla a la pila de entrada.

      Eliminar
  4. y como es posible visualisar el resultado de la esprecion algebraica por ejemplo :(4*2)+(4*2) =16

    ResponderEliminar
    Respuestas
    1. Primero tienes que pasar la expresión "(4*2)+(4*2)" a notación Postfija que da como resultado "4 2 * 4 2 * +".
      Seguidamente calcularla con el siguiente codigo:
      http://censorcosmico.blogspot.com.es/2012/09/evaluar-expresion-postfija-usando-pilas.html

      Y si quieres calcular el resultado de la expresión directamente:
      http://censorcosmico.blogspot.com.es/2012/06/obtener-el-resultado-numerico-de-una.html

      Eliminar
  5. Porq colocaste el while en los casos 3 y 4 no vastaria un IF

    ResponderEliminar
  6. por que no usas el caso 3, la potencia no la recorre?

    ResponderEliminar
    Respuestas
    1. Prueba de eliminar linea del caso 3 "case 3:" y entenderás el porqué.
      Un saludo.

      Eliminar
    2. por que no tiene nada el caso 3 yo la elimine y no hace nada

      Eliminar
    3. tampoco entiendo por q?? y tengo más preguntas

      Eliminar
  7. como se aria para que marque si la expresión introducida no es posible pasarla ejem: 5++

    ResponderEliminar
  8. Buenas tardes, oye una pregunta, de donde sacas esto package infixpostfix4; me seria de mucha ayuda este código.
    Muchas gracias.

    ResponderEliminar
    Respuestas
    1. Esa linea la genera automaticamente la IDE Netbeans. (infixpostfix4 es el nombre en el que guardamos el proyecto).

      Eliminar
  9. buenas tardes, una pregunta y si quiero evaluar una expresión ya dada en postfija por el usuario que código podría usar? gracias!

    ResponderEliminar
    Respuestas
    1. http://censorcosmico.blogspot.com.es/2012/09/evaluar-expresion-postfija-usando-pilas.html

      Eliminar
  10. como paso un postfijo a infijo? ayudaaa

    ResponderEliminar
  11. buen programa :) corre excelente aunque no entiendo muy bien algunas cosas como el funcionamiento del .peek,tambien esos dos caso que estan vacios hehe

    ResponderEliminar
  12. Porq no sirve para calcular una potencia?

    ResponderEliminar
  13. Que linea se le puede agregar para que funcione

    ResponderEliminar
  14. Podrías darme el caso de la potencia

    ResponderEliminar
  15. una pregunta y si quiero evaluar tambien el operador % y ^ como seria entonces el programa?

    ResponderEliminar
    Respuestas
    1. Darle al operador "%" la misma preferencia que "*" y "/" (preferencia = 4):
      if (op.equals("*") || op.equals("/") || op.equals("%")) prf = 4;

      En este ejemplo no evalua, sino que convierte la notacion infija a postfija.

      Eliminar
  16. y como hago si me piden el mismo codigo pero con operandos mayores a 9?

    ResponderEliminar
  17. Que tal como vas, mi pregunta es la siguiente, porque apilas la expresión de derecha a izquierda
    for (int i = arrayInfix.length - 1; i >= 0; i--) {
    E.push(arrayInfix[i]);
    }
    no se puede de izquierda a derecha?
    GRACIAS

    ResponderEliminar
    Respuestas
    1. Estamos trabajando con "Pilas" y eso implica que el primero que entra es el último en salir (metodo LIFO). En nuestro ejemplo necesitamos invertir el orden de la cadena para la entrada de los valores en la Pila.
      Si quisieras hacer de izquierda a derecha habría que utilizar las "Colas" y no las "Pilas", el primero que entra es el primero en salir (metodo FIFO).

      Eliminar
    2. AAA bien bien entiendo Gracias por aclararme eso Te lo agradezco muchas gracias ;)

      Eliminar
  18. Quisera que me ayudes con una exprecion matematica un método que valide el ingreso de la expresión infija. en caso haya algún error, el programa debe informarlo. Ejemplos de errores: parèntesis incorrectos, opradores seguidos, etc. (A+B *C )A-H( A+*P A/B-)

    ResponderEliminar
    Respuestas
    1. Se me ocurre usar las "Expresiones Regulares". http://censorcosmico.blogspot.com.es/2012/02/expresiones-regulares-i-tabla-de.html
      En tu caso para validar una formula matematica o ecuación el patrón seria siguiente:
      " /(([\+\-\/\*\^]?)([(]*(([(]?(([+-]?\d+[.,]?(\d+)?)([e][+-]\d+)?)[)]?)|([(]?value[)]?))[)]*)?(([(]*([(]?(([+-]?\d+[.,]?(\d+)?)([e][+-]\d+)?)[)]?)|([(]?value[)]?))[)]*)?([\+\-\/\*\^])([(]*(([(]?(([+-]?\d+[.,]?(\d+)?)([e][+-]\d+)?)[)]?)|([(]?value[)]?))[)]*))+/g ".

      Eliminar
  19. Buen día, si quisiera reemplazar el operador ^ por ** como seria la solución?. Te agradecería una respuesta oportuna

    ResponderEliminar
  20. no corre mi programa, no tiene void, podria acompletarlo

    ResponderEliminar
  21. Si se quieren agregar mas operaciones como factorial (!) que tiene mayor jerarquía que la multiplicación pero menor que la potencia, como debería hacerse el cambio en el switch?

    ResponderEliminar
  22. Que tal amigo viendo tu programa si funciona y muy bien hecho sabes yo quiero ver si me puedes ayudar con un programa similar solo que en lugar de pasar de infija a postfija que me traslade a prefija ya que tengo un proyecto en la U pero la verdad no se como realizarlo honestamente se me dificulta usar java y le necesito crear una interface grafica te agradeceria muxo amigo si me pudieras ayudar

    ResponderEliminar
  23. hola, como puedo agregar la notación prefija y el resultado de de la operación??????

    ResponderEliminar
  24. Amigo eres un maestro, muchas gracias por el código y por la explicación.

    ResponderEliminar
  25. Hombre tu codigo tiene un error cuando se usa ^

    ResponderEliminar
  26. Buenas tardes una pregunta que hace esta linea mejor dicho que compara(pref(E.peek()))

    ResponderEliminar
    Respuestas
    1. Esa linea devuelve la preferencia de carácter de la cima de la pila de entrada. Si por ejemplo la cima de la pila de entrada tiene el caracter "+", devolverá su preferencia en este caso el valor 3.

      Eliminar
  27. Disculpa para que metes el array en la pila?

    ResponderEliminar
    Respuestas
    1. Uso el array para invertir el orden de la cadena para la entrada de los valores en la Pila.

      Eliminar
  28. Hola disculpa, si ya tengo el convertidor de infijo a posfijo, ahora como le ago para que me acepte valores y que me aga las operaciones correspondientes?? ayuda son principiante

    ResponderEliminar
  29. Hola, disculpa porque el 99? podrias explicarme el programa mas a detalle?
    //Jerarquia de los operadores
    private static int pref(String op) {
    int prf = 99;
    if (op.equals("^")) prf = 5;
    if (op.equals("*") || op.equals("/")) prf = 4;
    if (op.equals("+") || op.equals("-")) prf = 3;
    if (op.equals(")")) prf = 2;
    if (op.equals("(")) prf = 1;
    return prf;
    }
    }

    ResponderEliminar
    Respuestas
    1. Ahí tienes la explicación con más detalle:
      http://censorcosmico.blogspot.com.es/2012/09/primeros-pasos-para-conversion-infijo.html

      Eliminar
    2. Explicación x favor
      try {
      //Algoritmo Infijo a Postfijo
      while (!E.isEmpty()) {
      switch (pref(E.peek())){
      case 1:
      P.push(E.pop());
      break;
      case 3:
      case 4:
      while(pref(P.peek()) >= pref(E.peek())) {
      S.push(P.pop());
      }
      P.push(E.pop());
      break;
      case 2:
      while(!P.peek().equals("(")) {
      S.push(P.pop());
      }
      P.pop();
      E.pop();
      break;
      default:
      S.push(E.pop());
      }
      }

      Eliminar
  30. LO QUE NO ENTIENDO ES POR QUE EL "CASE 3" NUNCA CERRO CON "BREACK"
    O EN QUE MOMENTO SE USO???
    NECESITO LA RESPUESTA GRACIAS

    ResponderEliminar
  31. me gustaria conocer el codigo dada una exprecion infija a prefija ya que no logro esa operacion

    ResponderEliminar
  32. Buenos días. Esta genial el código. Tengo dos dudas. a) Qué hago para poner expresiones con potencias?. Si lo que quiero evaluar son potencias, escritas de la forma \frac{2}{33} (código latex). Cómo podría introducirlas a la pila. Muchísimas gracias.

    ResponderEliminar
  33. Evalué con esta expresión ((5+9^(1/2))/(4+4)+2)^3-(5*2) y su resultado postfijo es este: 5 9^ 1 2 / + 4 4 + / 2 + ^3 5 2 * -
    PERO. el ultimo ejercicio de este video https://www.youtube.com/watch?v=d7UZdz_yGXQ evaluando la misma expresión da como resultado 5 9 1 2 / ^ + 4 4 +/ 2 + 3 ^ 5 2 * -... me gustaria me ayuden a entender si esta bien el programa si se equivocó el programa o si esta mal el video o está bien el video... o si es lo mismo. Muchas Gracias

    ResponderEliminar
    Respuestas
    1. Añadiendo a lo anterior acabo de probar el codigo de evaluar la expresion postifja http://censorcosmico.blogspot.com.co/2012/09/evaluar-expresion-postfija-usando-pilas.html que esta recomendado en los comentarios con la expresion que arroja el primer programa 5 9^ 1 2 / + 4 4 + / 2 + ^3 5 2 * - y como resultado tengo error.

      Eliminar
    2. por lo q veo no esta en el segundo codigo implementado la potencia (^)

      Eliminar
  34. una pregunta, como se hace para que una expresión infija se convierta a prefija???

    ResponderEliminar
  35. Encontre un problema, intente solcionarlo pero por ejemplo si la expresion empieza con -2+3 la expresion en postfija seria -2 3 +. En esta caso la convierte en 2 - 3 + y eso para evaluarlo genera un error. Si alguien tiene la solucion para ello me gustaria saberlo

    ResponderEliminar
    Respuestas
    1. A este algoritmo aún le queda margen de mejora, como en este caso y operaciones con potencias "^" que tampoco da el resultado correcto. Espero solventarlos en posteriores revisiones.
      Saludos,

      Eliminar
  36. Disculpa que debo cambiar en el algoritmo para que cambie de infijo a prefijo y de antemano muchas gracias
    try {
    //Algoritmo Infijo a Postfijo
    while (!E.isEmpty()) {
    switch (pref(E.peek())){
    case 1:
    P.push(E.pop());
    break;
    case 3:
    case 4:
    while(pref(P.peek()) >= pref(E.peek())) {
    S.push(P.pop());
    }
    P.push(E.pop());
    break;
    case 2:
    while(!P.peek().equals("(")) {
    S.push(P.pop());
    }
    P.pop();
    E.pop();
    break;
    default:
    S.push(E.pop());
    }
    }

    ResponderEliminar
  37. Hola, alguien que me ayude a sacar la ecuación de la notación polaca inversa? esta en este método.Por favor

    public double evaluaPolaca(String s) {

    double resultado = 0;
    String v[] = s.split(",");
    PilaS pila = new PilaS();
    for (String x : v) {


    // Aqui me falta la ecuacion



    }
    resultado=Double.parseDouble(pila.pop().getDato());
    return resultado;
    }
    }

    ResponderEliminar
  38. Tienen un codigo que: de infija pasa a postfija y visceversa y de el resultado de la operacion en el mismo codigo?

    ResponderEliminar

Con la tecnología de Blogger.