/*
  Ejercicio # 4
  Nombre: Manejo de Pilas
  Autor: Carlos Rolando Calán Ajquill
  Fecha: 24/06/06 00:45
  Descripción: Programa que realiza un recorrido de una expresion infija para
  convertirla a una notacion postfija
  Versión: 1.0 
*/
#include <cstdlib>
#include <iostream>
#include <stdio.h>
#include <conio.h>

using namespace std;
//Tipo definido de datos para manejar datos booleanos
typedef enum {False,True} Booleano; 
//Tipo definido de datos para manejar la direccion de la pila
typedef enum {izq, igual, der, none} Par; 
//Matriz de elementos para verificar cuales son los simbolos que va aceptar 
//el programa
char Simbolos[4][3]={{'(',')','\0'},{'-','+','\0'},{'/','*','\0'},{'^','\0','\0'}}; 
//Procedimiento para limpiar los datos de la pila
void Limpiar(char[], int);
//Procedimiento para insertar datos a la pila
void Insertar(char[], char []); 
//Procedimiento para Agregar datos a al  pila
void Agregar(char[], char);
//Procedimiento para leer datos de la pila
void Leer(char[]);
//Procedimiento para ver la expresion postfija
void Rec_Exp_Pos(char[]); 
//Procedimiento para ver la posicion de los simbolos en la expresion infija
void Conv_Pos(char[], char []);
//Para ver la prioridad de los simbolos que son aceptados por el programa
int Prioridad(char, char); 
//Para saber la longitud de la expresion que ingreso el usuario
int Longitud(char []); 
Par VerificarLaCadena(char []); 
Booleano VerificarSimbolo(char); 

int main(int argc, char *argv[])
{
  char Exp[50], E1[50], EPOS[50];    
  Limpiar(EPOS, 50); 
  Limpiar(E1, 50); 
  do
  { 
    system("CLS");
    printf("\n \n \n");     
    printf("%s","\t \t \t UNIVERSIDAD MARIANO GALVEZ \n \n");     
    printf("%s","\t \t Proyecto Final Estructura De Datos \n");    
    printf("%s","\t \t Carlos Rolando Calan Ajquill    Junio/2006 \n");
    printf("%s","\t \t Carne: 0910-04-13429         5to. Semestre \n");
    printf("%s","\t \t ----------------------------------------------\n");    
    printf("%s","\t \t Ejercicio del Manejo de Pila(Expresion Infija)\n ");
    printf("%s","\t \t ----------------------------------------------\n\n");        
    printf("%s","Introduzca la expresion infija: \n"); 
    Leer(Exp); 
    if(VerificarLaCadena(Exp) != igual)
    { 
      printf("La expresion \'%s\' no es valida", Exp); 
      switch (VerificarLaCadena(Exp))
      { 
        case izq: printf("Le faltan parentesis derechos.");break; 
        case der: printf("Le faltan parentesis izquierdos.");break; 
        case none:
          printf("Ya que no es funcion valida.");break;
      }       
    } 
  } while (VerificarLaCadena(Exp) != igual);   
  Insertar(E1,Exp);   
  Conv_Pos(E1,EPOS); 
  printf("%s %s\n","Su conversion a Postfija es: ",EPOS); 
  getch(); 
  system("PAUSE"); 
} 

/*Esta funcion limpia los espacios en el texto ingresado*/ 
void Limpiar(char Text[], int n)
{ 
  int i; 
  for(i=0; i<n; i++)
    /*Cuando escribimos \0 es igual a NULL*/ 
    Text[i] = '\0'; 
} 

/*Hace lo mismo que Scanf("%[^\n]", Exp)*/ 
void Leer(char Exp[])
{ 
  int i; 
  for(i=0; (Exp[i] = getchar()) != '\n'; ++i); 
  Exp[i] = '\0'; 
} 

/*Calcula la prioridad entre exp1 y exp2 
-1 si exp1 < exp2 
0 si exp1 == exp2 
1 si exp1 > exp2*/ 
int Prioridad(char exp1, char exp2)
{ 
  int i,j,p1,p2; 
  for(i=0; i<4; i++) 
    for(j=0; j<3; j++)
    { 
      if(exp1==Simbolos[i][j]) 
        p1=i; 
      if(exp2==Simbolos[i][j]) 
        p2=i; 
    } 
    if(p1 < p2) 
      i=-1; 
    else 
      if(p1 == p2) 
        i=0; 
      else 
        if(p1 > p2) 
          i=1; 
  return(i); 
} 

/*Hace lo mismo que strlen(text)*/ 
int Longitud(char text[])
{ 
  int n; 
  for(n=0; text[n] != '\0' ; ++n); 
  return(n); 
} 

/*Agrega la cadena B en A*/ 
void Insertar(char A[],char B[])
{ 
  int n1, n2, i; 
  n1 = Longitud(A); 
  n2 = Longitud(B); 
  for(i=n1; i<(n1+n2); i++) 
  A[i]= B[i-n1]; 
  A[i]= '\0'; 
} 

/*Verifica si text es una cadena valida*/ 
Par VerificarLaCadena(char text[])
{ 
  int i, n, cont1, cont2, TOPE; 
  char PILA[50], elem; 
  Par val = none; 
  n = Longitud(text); 
  if (n > 0)
  { 
    TOPE = 0; 
    cont1 = cont2 =0; 
    for(i=0; i<n; i++)
    { 
      elem = text[i]; 
      if (elem == '(')
      { 
        PILA[TOPE] = elem; 
        TOPE++; 
        PILA[TOPE] = '\0';
      } 
      else 
        if (elem == ')') 
          if (TOPE > 0)
          { 
            if (PILA[TOPE-1] == '(')
            { 
              TOPE--; 
              PILA[TOPE]='\0';
            } 
          }
          else
          { 
            PILA[TOPE] = elem; 
            TOPE++; 
            PILA[TOPE] = '\0';
          } 
    }  
    if (TOPE > 0)
    { 
      for(i=0; i<TOPE; i++)
      { 
        if (PILA[i] == '(') 
          cont1++; 
        if (PILA[i] == ')') 
          cont2++; 
      } 
      if (cont1 < cont2) 
        val = der; 
      if (cont1 > cont2) 
        val = izq; 
    } 
    else 
      val = igual; 
  }
  else 
    val = none; 
  return(val); 
} 

/*Verifica si Expr es simbolo o no*/ 
Booleano VerificarSimbolo(char Expr)
{ 
  int i, j; 
  Booleano val; 
  val = False; 
  for(i=0; i<4; i++) 
    for(j=0; j<3; j++) 
      if(Expr == Simbolos[i][j]) 
        val=True; 
  return(val); 
} 

/*Agrega un caracter a la cadena Exp1*/ 
void Agregar(char Exp1[], char Exp2)
{ 
  int n; 
  n = Longitud(Exp1); 
  Exp1[n] = Exp2; 
} 

/*Elimina el primer elemento*/ 
void Rec_Exp_Pos(char Text[])
{ 
  int i,n; 
  n = Longitud(Text); 
  for(i=0; i<(n-1); i++) 
    Text[i]= Text[i+1]; 
  Text[i] = '\0';
} 

/*Convierte una epresion EI (Infija) a una expresion EPOS (Postfija)*/ 
void Conv_Pos(char EI[],char EPOS[])
{ 
  int TOPE, n; 
  char Simbolo, PILA[50]; 
  Limpiar(PILA, 50); 
  /*Hacer TOPE <- -1*/ 
  TOPE=-1; 
  n = Longitud(EI); 
  /*Repetir Mientras EI sea diferente a cadena vac¡a*/ 
  while(EI[0]!='\0')
  { 
    /*Tomar el s¡mbolo m s a la izquierda de EI*/ 
    Simbolo=EI[0]; 
    /*Recortamos la Expresi¢n*/ 
    Rec_Exp_Pos(EI); 
    n-=1; 
    /*Si el s¡mbolo es par‚ntesis izquierdo*/ 
    if (Simbolo=='(')
    { 
      /*Poner s¡mbolo en la pila*/ 
      TOPE+=1; 
      PILA[TOPE]=Simbolo; 
    } 
    else 
      /*Si el s¡mbolo es par‚ntesis derecho*/ 
      if(Simbolo==')')
      { 
        while(PILA[TOPE]!='(')
        { 
          /*Agregamos lo que hay en el tope de la pila*/ 
          Agregar(EPOS,PILA[TOPE]); 
          PILA[TOPE]='\0'; 
          TOPE-=1; 
        } 
        /*Sacamos el par‚ntesis izquierdo de la pila*/ 
        PILA[TOPE]='\0'; 
        TOPE-=1; 
      } 
      else 
       /*Si es operando*/ 
       if(VerificarSimbolo(Simbolo)==False)
       { 
       /*Insertar contenido de Simbolo a EPOS*/ 
       Agregar(EPOS,Simbolo); 
       } 
       else
       { 
         /*Si la Pila contiene algo*/ 
         if(Longitud(PILA)>0)
         { 
           /*Mientras el operador sea <= al que se encuentra 
             al tope de la pila*/ 
           while(Prioridad(Simbolo, PILA[TOPE]) <= 0)
           { 
             /*Insertar lo que hay al tope de la pila*/ 
             Agregar(EPOS, PILA[TOPE]); 
             /*Borramos lo que hay al tope de la pila*/ 
             PILA[TOPE] = '\0'; 
             TOPE-=1; 
             if(TOPE < 0) 
               break; 
           } 
         } 
         /*Agregamos el s¡mbolo al tope de la pila*/  
         TOPE+=1; 
         PILA[TOPE]=Simbolo; 
       } 
  } 
  /*Agregamos lo que quedo en la pila*/ 
  while(TOPE>=0)
  { 
    Agregar(EPOS,PILA[TOPE]); 
    TOPE-=1; 
   } 
}