Jason Igneel

Expresión In-fija a Posfija en C/C++ explicando paso a paso como se llega a la Posfija y obteniendo el resultado de la función ingresada.
Echo en Dev C++,





Código:

#include <cstdlib>
#include <iostream>
#include <string>
#include <stack>
#include <cmath>

using namespace std;

/* Operadores matematicos */
#define N_operators 6
const string operators[N_operators] = {"+", "-", "*", "/", "%", "^"};
int precedences[N_operators] = {1, 1, 2, 2, 2, 3};

bool is_operator( const string );
int precedence( const string );

int main() {

string infix, postfix, token;
stack <string> standby;
stack <double> result;
size_t i;
char c;
double A, B;

  system("color f9");
/* Cadena de entrada */
cout <<"\n\tGRUPO N 1  \n"<<endl;
    cout <<"\t Programa para ingresar una exprecion Infija a posfija \n y resolver la exprecion Posfija.  "<<endl;
cout << "\nEscriba la expresion infija: ">
getline( cin, infix );
cout << endl;

/*************************************************************
 PRIMERA PARTE: Procesar la cadena infijo, y crear posfijo
*************************************************************/

for ( i = 0; i < infix.size(); i++ ) {
/* esto debe cambiar luego a un token o palabra devuelta por
* el analizador léxico */
c = infix[i];
token.clear();
token += c; /* parece burdo, pero no conozco mejor manera de
* crear un string a partir de un unico caracter */

/* es un espacio: despreciar */
if ( c == ' ' ) continue;

cout << " '" << c << "'" << endl;

/* es un carácter numérico: pasar al posfijo */
if ( c >= '0' && c <= '9' ) {
cout << "\tes numero: pasado a posfijo" << endl << endl;
postfix = postfix + " " + c;
continue;
}

/* si se lee un operador: sacar de la pila y pasar al postfijo
* todos los operadores con una precedencia mayor o igual a la
* suya, y depositar el mismo en la pila */
if ( is_operator( token ) ) {
cout << "\tes operador:" << endl;
while ( !standby.empty() && precedence( standby.top() )
>= precedence( token ) ) {
cout << "\tpasado operador '" + standby.top() +
"' de la pila a posfijo" << endl;
postfix = postfix + " " + standby.top();
standby.pop();
}
standby.push( token );
cout << "\tcolocar '" << token << "' en la pila" << endl << endl;
continue;
}

/* si se lee "(": colocar en la pila */
if ( token == "(" ) {
cout << "pasado a posfijo" << endl << endl;
standby.push( token );
continue;
}

/* si se lee ")": retirar de la pila hasta encontrar '(', y pasar
* los elementos retirados a posfijo, luego descartar el "(" */
if ( token == ")" ) {
while ( !standby.empty() && standby.top() != "(" ) {
cout << "\tpasado operador '" + standby.top() +
"' de la pila a posfijo" << endl << endl;
postfix = postfix + " " + standby.top();
standby.pop();
}
if ( !standby.empty() )
standby.pop(); /* descartar el "(" */
}
}


/* extraer de la pila cualquier operador restante y pasarlo a la cadena posfijo */
while ( !standby.empty() ) {
cout << "Pasado operador '" + standby.top() +
"' de la pila a posfijo" << endl << endl;
postfix = postfix + " " + standby.top();
standby.pop();
}

/* Imprimir el posfijo */
cout << "Posfijo es: \n\t" << postfix << endl << endl;

/****************************************************************
 SEGUNDA PARTE: Procesar la cadena posfijo, y devolver resultado
****************************************************************/

A = 0;
cout << "Evaluando la expresion ..." << endl;
for ( i = 0; i < postfix.size(); i++ ) {

c = postfix[i];
token.clear();
token += c;

/* si se lee un operando (caracter numerico), depositar en la pila */
if ( c >= '0' && c <= '9' ) {
result.push( c - '0' );
continue;
}

/* si se lee un operador binario, poner en A y B los últimos dos argumentos
* de la pila y operarlos, guardando el resultado en la pila */
if ( is_operator( token ) ) {
if ( !result.empty() ) {
B = result.top();
result.pop();
}
else {
cout << "Argumentos insuficientes para '" << c << "'" << endl;
return -1;
}

if ( !result.empty() ) {
A = result.top();
result.pop();
}
else {
cout << "Argumentos insuficientes para '" << c << "'" << endl;
return -1;
}

cout << "\toperar " << A << token << B << " = ";
if ( token == "+" ) {
A += B;
result.push( A );
}
else if ( token == "-" ) {
A -= B;
result.push( A );
}
else if ( token == "*" ) {
A *= B;
result.push( A );
}
else if ( token == "/" ) {
A /= B;
result.push( A );
}
else if ( token == "%" ) {
A = (int )A % (int )B;
result.push( A );
}
else if ( token == "^" ) {
A = pow(A, B);
result.push( A );
}
cout << A << endl;
}
}

if ( !result.empty() )
cout << endl << "El resultado es: " << result.top() << endl;

return 0;
}

/* Verdadero si el token corresponde a un operador. */
bool is_operator( const string token ) {

for ( int i = 0; i < N_operators; i++ )
if ( operators[i] == token )
return true;

return false;
}

/* Devuelve la precedencia del operador descrito por el
 * string token (-1 si no es un operador) */
int precedence( const string token ) {

for ( int i = 0; i < N_operators; i++ )
if ( operators[i] == token )
return precedences[i];

return -1;
}

En una PILA ingresaremos caracteres y números a una pila con las funciones Agregar, Eliminar, Mostrar y Destruir la pila.


Código:

#include<iostream>
#include<cstdlib>
using namespace std;

struct nodo{
    char let;// usamos char para poder obtener los caractere para la pila
    struct nodo *sgte;
};

typedef struct nodo *Puntero;

class Pila{
    public:
        Pila(void);
        void Apilar(int );
        int Desapilar(void );
        void tope(void);
        bool PilaVacia(void);
        void MostrarPila(void);
        void DestruirPila(void);

    private:
        Puntero Tope;

};
Pila::Pila(void){
    Tope=NULL;
}

bool Pila::PilaVacia(void){
    if(Tope==NULL)
        return true;
    else
        return false;
}

void Pila::Apilar(int x){

    Puntero p_aux;
    p_aux=new(struct nodo);
    p_aux->let=x;
    p_aux->sgte=Tope;
    Tope=p_aux;

}

//eliminara el elemento del tope de la pila ingresado
int Pila::Desapilar(void){
    int x;
    Puntero p_aux;
    if(Tope==NULL)
        cout<<"\n\n\tLa Pila esta Vacia.";
    else{
        p_aux=Tope;
        x=p_aux->let;
        Tope=Tope->sgte;
        delete(p_aux);
    }
    return x;
}
//NOS MOSTRARA TOTODS LOS ELELMENTOS INGRESADOS ASI COMO LOS CARACTERES Y NUMEROS EN LA PILA
void Pila::MostrarPila(void){
    Puntero p_aux;
    p_aux=Tope;

    while(p_aux!=NULL){
        cout<<"\t\t\t "<<p_aux->let<<endl;
        p_aux=p_aux->sgte;
    }
}
//DESTRUYE LA PILA POR COMPLETAMENTE DEGANDOLA VACIA.
void Pila::DestruirPila(void){
    Puntero p_aux;

    while(Tope!=NULL){
            p_aux=Tope;
            Tope=Tope->sgte;
            delete(p_aux);
    }
}

void menu(void)
{

    cout<<"\n\t        PILA CON CARACTERES Y NUMERSO      \n\n";
    cout<<" \t  1. AGREGAR A LA PILA "<<endl;
    cout<<" \t  2. ELIMINAR DE LA PILA "<<endl;
    cout<<" \t  3. MOSTRAR PILA    "<<endl;
    cout<<" \t  4. DESTRUIR PILA       "<<endl;
    cout<<" \t  5. SALIR        "<<endl;
    cout<<"\t ESCOGA UNA OPCION: ";
}

int main(void ){
//clolor de pantalla
    system("color f9");
    Pila pila;
    char x;
    int op;

    do
    {
        menu();  cin>> op;

        switch(op)
        {
            case 1: cout<< "\n\t INGRESE NUMERO Para la PILA: "; cin>> x;
                    pila.Apilar(x);
                    cout<<"\n\n\t\tNumero ( " << x << " ) agregado en la pila.\n\n";
                    break;

            case 2:
                    if(pila.PilaVacia()==true)
                        cout<<"\n\n\tLa Pila esta Vacia.";
                    else{
                        x = pila.Desapilar( );
                        cout<<"\n\n\tNumero ( "<<x<<" ) eliminado de la PILA\n";
                        }
                    break;


            case 3:
                    cout << "\n\n\t\t MOSTRANDO LA PILA\n\n";
                    if(pila.PilaVacia()!=true)
                        pila.MostrarPila(  );
                    else
                        cout<<"\n\n\tLa Pila esta Vacia."<<endl;
                    break;


            case 4:
                    pila.DestruirPila(  );
                    cout<<"\n\n\t\tPila ha DESTRUIDA\n\n";
                    break;

         }

        cout<<endl<<endl;
        system("pause");
        system("cls");

    }while(op!=5);

return 0;
}