pasar una expresión infijo a postfijo

luiskbala
12 de Abril del 2005
necesito ayuda para crear un método que pase una expresión en infijo a postfijo lo mas rapido que alguien pueda ayudarme

raconte
12 de Abril del 2005
aca tengo un algoritmo poderoso para eso. Yo mismo lo diseñé, claro que me basé en uno que esta en el libro de estructura de datos en Pascal.

/*
* Infijo.java
*
* Created on 11 de abril de 2005, 17:06
*/

package postfijo;

/**
*
* @author usuario
*/

import java.util.*;

public class Infijo {

private int [][] matrix = null;
private ArrayList lista = null;
/** Creates a new instance of Infijo */
public Infijo() {
matrix = this.crearMatrix();

for (int x = 0; x < matrix.length; x++){
for (int y = 0; y < matrix.length; y++){
System.out.print(matrix[x][y] + "t");
}
System.out.print("n");
}

}

public int [][] crearMatrix(){
int [][] m = { {1,1,0,0,0,0,1} ,
{1,1,0,0,0,0,1} ,
{1,1,1,1,0,0,1} ,
{1,1,1,1,0,0,1} ,
{1,1,1,1,1,0,1} ,
{0,0,0,0,0,0,0} ,
{2,2,2,2,2,2,2}
};
return m;
}

public boolean Operando(String c){
if (!c.equals("+") &&
!c.equals("-") &&
!c.equals("*") &&
!c.equals("/") &&
!c.equals("^") &&
!c.equals("(") &&
!c.equals(")") )
return true;
return false;
}

public boolean prioridad(char op1, char op2,int [][] m){
boolean res = false;
int i = 0;
int j = 0;

switch (op1){
case '+': i = 0;break;
case '-': i = 1;break;
case '*': i = 2;break;
case '/': i = 3;break;
case '^': i = 4;break;
case '(': i = 5;break;
}

switch (op2){
case '+': j = 0;break;
case '-': j = 1;break;
case '*': j = 2;break;
case '/': j = 3;break;
case '^': j = 4;break;
case '(': j = 5;break;
case ')': j = 6;break;
}
res = m[i][j] == 1;
return res;
}

public String tope (Stack pila){
String caracterTope = (String)pila.peek();
return caracterTope;
}

public ArrayList procesarPostfijo(ArrayList listaInfijo , int [][] m){
ArrayList lista = new ArrayList();
int i = 0;
int j = 0;
String cadena = null;
String temp = null;

Stack pila = new Stack();
Elemento elemento = null;

for (int x = 0; x < listaInfijo.size();x++){
cadena = (String)listaInfijo.get(x);

if (this.Operando(cadena)){
elemento = new Elemento();
elemento.tipo = "V";
elemento.valor = cadena;
lista.add(elemento);
}else{
System.out.println("Procesando Operador : [" + cadena + "]");
while (!pila.empty() && this.prioridad(this.tope(pila).charAt(0),cadena.charAt(0),m) ){
//System.out.println("op1 {" + this.tope(pila).charAt(0) + "} op2 {" + cadena.charAt(0) + "}");
temp = (String)pila.pop();

elemento = new Elemento();
elemento.tipo = "R";
elemento.valor = temp;
lista.add(elemento);

}

if (cadena.equals(")")){
temp = (String)pila.pop();
}else{
pila.push((String)cadena);
}

}

}

while(!pila.empty()){
temp = (String)pila.pop();
elemento = new Elemento();
elemento.tipo = "R";
elemento.valor = temp;
lista.add(elemento);
}

return lista;
}

public void imprimirListaPostfijo(ArrayList lista){
if (lista != null){
System.out.println("============================");
System.out.println("Lista PostFijo");
System.out.println("============================");
for(int x = 0; x < lista.size();x++){
Elemento elemento = (Elemento)lista.get(x);
System.out.print("[" + elemento.tipo + "]" + "[" + elemento.valor + "]t");
}
System.out.println("n============================");
}
}

public void setListaPostFijo(ArrayList lista){
this.lista = lista;
}

public ArrayList getListaPostFijo(){
ArrayList lista = (ArrayList)this.lista;
return lista;
}

public ArrayList convertirPostFijo(){
ArrayList listaDef = null;
listaDef = this.procesarPostfijo((ArrayList)this.getListaPostFijo(), this.matrix);
return listaDef;
}

public double evaluarPostFijo(ArrayList listaPostFijo){
double resul = 0;
double a = 0;
double b = 0;
double r = 0;
String temp1 = null;
String temp2 = null;
String temp3 = null;

Stack pila = new Stack();
Elemento elemento = null;

if (listaPostFijo != null){
for (int x = 0; x < listaPostFijo.size();x++){
elemento = (Elemento)listaPostFijo.get(x);
if (elemento.tipo.equals("V")){
pila.push(elemento.valor);
}else{
a = 0;
b = 0;
temp1 = (String)pila.pop();
temp2 = (String)pila.pop();

if (temp1 != null)
a = Double.parseDouble(temp1);

if (temp2 != null)
b = Double.parseDouble(temp2);

r = this.resultado(a,b,elemento.valor.charAt(0));
pila.push(String.valueOf(r));
}
}

temp3 = (String)pila.pop();
if (temp3 != null)
resul = Double.parseDouble(temp3);
}
return resul;
}


public double resultado(double a, double b, char c){
double resul = 0;
switch (c){
case '+': resul = a + b; break;
case '-': resul = a - b; break;
case '*': resul = a * b; break;
case '/': resul = a / b; break;
case '^': resul = Math.exp(b * Math.log(a));break;
}
return resul;
}


public class Elemento {

public String tipo;
public String valor;

public Elemento() {
this.tipo = null;
this.valor = null;
}



}
}

Esta es la clase principal


/*
* po.java
*
* Created on 11 de abril de 2005, 17:41
*/

package postfijo;

/**
*
* @author usuario
*/
import postfijo.Infijo;
import java.util.*;

public class po {

/** Creates a new instance of po */
public po() {
}

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here

Infijo inf = new Infijo();
double valorDefinitivo = 0;
ArrayList listaInfijo = new ArrayList();

/*
listaInfijo.add("(");
listaInfijo.add("5");
listaInfijo.add("+");
listaInfijo.add("8");
listaInfijo.add(")");
listaInfijo.add("*");
listaInfijo.add("7");
*/


listaInfijo.add("358400");
listaInfijo.add("*");
listaInfijo.add("(");
listaInfijo.add("1");
listaInfijo.add("+");
listaInfijo.add("0.03");
listaInfijo.add(")");



inf.setListaPostFijo(listaInfijo);
ArrayList listaDefinitiva = inf.convertirPostFijo();
inf.imprimirListaPostfijo(listaDefinitiva);

valorDefinitivo = inf.evaluarPostFijo(listaDefinitiva);
System.out.println("valorDefinitivo : " + valorDefinitivo);

}

}



Espero que te sirva.

tenes que meter todo dentro de una carpeta postfijo y configurar bien el paquete.