Códigos Pilas

EXPRESIONES INFIJAS:

Para evaluar expresiones, se hace uso de algunas técnicas utilizadas en el diseño de compiladores. 
Las expresiones según su notación pueden ser: 
Notación infija.- operando-operador-operando. Ejemplo: A + B Notación prefija.- operador-operando-operando. Ejemplo: + A B Notación postfija.- operando-operando-operador. Ejemplo: A B + 
Al hacer uso de las expresiones infijas, la expresión 1 + 5; consiste de un operador binario junto con sus operandos (argumentos). Una expresión más elaborada es: 1 + 5 * 2; la cual matemáticamente es evaluada a 11, debido a que, el operador * (de multiplicación) tiene mayor precedencia que el de suma.
Si no se tiene en cuenta la precedencia, la respuesta será 12. 
Las expresiones en postfija, proporcionan un mecanismo directo de evaluación; existiendo algoritmos de pila para la resolución.

CONVERSIÓN EXPRESIÓN INFIJA A POSFIJA

El siguiente algoritmo traduce una expresión en notación infija a notación postfija:

Entrada: Una lista que contiene los términos de la ecuación en notación infija (la notación habitual).

Salida: Una lista que contiene los términos de la ecuación en notación postfija.

Crear pila y la lista de salida, inicialmente vacias.

Datos locales: Una pila, que va a contener operadores y paréntesis izquierdos. INICIO MIENTRAS lista de entrada no este vacia y

Insertar E al final de la lista de salida

no se ha encontrado ningun error HACER Extraer el primer termino de la lista (lo llamaremos E) SEGUN-SEA E CASO E es número : CASO E es la variable x :

MIENTRAS La pila no este vacía y

Insertar E al final de la lista de salida CASO E es un paréntesis izquierdo : Insertar E en la pila CASO E es un paréntesis derecho : su cima no sea un paréntesis izquierdo HACER

Se ha detectado un ERROR 2

Extraer elemento de la pila Insertarlo al final de la lista de salida FIN-MIENTRAS SI Encontramos el parentesis izquierdo ENTONCES Extraerlo de la pila y destruirlo SINO FIN-SI Destruir E

FIN-MIENTRAS

CASO E es un operador : MIENTRAS La pila no este vacía y su cima sea un operador de precedencia mayor o igual que la de E HACER Extraer elemento de la pila Insertarlo al final de la lista de salida

FIN

Insertar E en la pila FIN-SEGUN-SEA FIN-MIENTRAS MIENTRAS Pila no esté vacía HACER Extraer elemento de la pila Insertarlo al final de la lista de salida FIN-MIENTRAS Destruir pila

Ejemplo de pila

import java.util.Scanner;
       public class Pila {
 
    class Nodo {
        int info;
        Nodo sig;
    }
 
    private Nodo raiz;
    
    public Pila () {
        raiz=null;
    }
    
    public void insertar(int x) {
     Nodo nuevo;
        nuevo = new Nodo();
        nuevo.info = x;
        if (raiz==null)
        {
            nuevo.sig = null;
            raiz = nuevo;
        }
        else
        {
            nuevo.sig = raiz;
            raiz = nuevo;
        }
    }
    
    public int extraer ()
    {
        if (raiz!=null)
        {
            int informacion = raiz.info;
            raiz = raiz.sig;
            return informacion;
        }
        else
        {
            return Integer.MAX_VALUE;
        }
    }
    
    public void imprimir() {
        Nodo reco=raiz;
        System.out.println("Listado de todos los elementos de la pila.");
        while (reco!=null) {
            System.out.print(reco.info+"-");
            reco=reco.sig;
        }
        System.out.println();
    }
    
    public static void main(String[] ar) {
        Pila pila1=new Pila();
        pila1.insertar(10);
        pila1.insertar(40);
        pila1.insertar(3);
        pila1.imprimir();
        System.out.println("Extraemos de la pila:"+pila1.extraer());
        pila1.imprimir();        
    }
}
}

Ejemplo de pila

import java.util.Scanner;
 public class Parser
{
 private static final int EOL = 0;
 private static final int VALUE = 1;
 private static final int OPAREN = 2;
 private static final int CPAREN = 3;
 private static final int EXP = 4;
 private static final int MULT = 5;
 private static final int DIV = 6;
 private static final int PLUS = 7;
 private static final int MINUS = 8;
 private static final int FUNCT = 9;
 private static String[] function =
 {
 "sqrt","sin",
 "cos","tan",
 "asin","acos",
 "atan","log",
 "floor","eXp"
 };
 private String string;
 private Stack opStack; // Operator stack for
conversion
 private Stack postfixStack; // Stack for postfix
machine
 private StringTokenizer str; // StringTokenizer
stream
 // . . . continua codigo de los metodos de la clase .
. .
 public double getValue(double x)
 {
 return getValue(x,0,0);
 }

 public double getValue(double x,double y)
 {
 return getValue(x,y,0);
 }
 public double getValue(double x,double y,double z)
 {
 // for each call
 opStack = new Stack( );
 postfixStack = new Stack( );
 str = new StringTokenizer(string,"+*-/^()xyz ",true);
 opStack.push( new Integer( EOL ) );
 EvalTokenizer tok = new EvalTokenizer(str,x,y,z);
 Token lastToken;
 do
 {
 lastToken = tok.getToken( );
 processToken( lastToken );
 } while( lastToken.getType( ) != EOL );
 if( postfixStack.isEmpty( ) )
 {
 System.err.println( "Missing operand!" );
 return 0;
 }
 double theResult = postFixTopAndPop( );
 if( !postfixStack.isEmpty( ) )
 System.err.println( "Warning: missing operators!"
);
 return theResult;
 }
}
}