/* Item.h */
typedef char Item;

/*
 * STACK.h 
 * INTERFACE: funcoes para manipular a pilha 
 */

void STACKinit(int);
 int STACKempty();
void STACKpush(Item);
Item STACKpop();
Item STACKtop();
void STACKfree();
void STACKdump(); 


/*
 *  polonesa.c
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Usado para simulacao e `debugging' */
/* coloque `= 1'  se voce quer ver uma simulacao e `= 0' se nao quer*/
enum {
  MOSTRE_ITEM  = 1, /* mostra o item sendo examinado */
  MOSTRE_EXPRESSAO = 1, /*  mostra a expressao em cada iteracao */
  MOSTRE_PILHA = 1  /* mostra o conteudo da pilha em cada iteracao */
};



/*
 * para_polonesa: recebe uma expressão infixa apontada por `infixa' e 
 *         devolve o endereco de um vetor que contem a correspondente 
 *         expressão polonesa.
 *
 * ATENCAO: a funcao supoe que a expressao infixa esta sintaticamente correta.
 *          Se a expressao for, digamos, "A+B)", ocorrera' "segmentation fault". 
 */
char *
para_polonesa (char *infixa) 
{
  char *polonesa; /* apontador para a expressao polonesa */
  int  n = strlen(infixa); /* comprimento da expressao infixa */
  int  i; /* percorre a expressao infixa */
  int  j; /* percorre a expressao posfixa */
  
  /* aloca area para guardas a expresao polonesa */
  polonesa = (char *) malloc ((n + 1) * sizeof(char));

  STACKinit(n); /* inicializa a pilha */

  /* examina cada item da expressao infixa */
  j = 0;
  for (i = 0; i < n; i++)
    {
      if (MOSTRE_ITEM) 
	{
          fprintf(stdout,"item: '%c'\n", infixa[i]);
	}

      switch (infixa[i]) 
	{
	  char item; /* auxiliar, recebe o elemento do topo da pilha */

	case '(': 
	  STACKpush('('); /* empilha */
	  break;
	  
	case ')':
	  while ((item = STACKpop()) != '(')  /* desempilha */
	    polonesa[j++] = item;
	  break;
	  
	case '+': 
	case '-': 
	  while (!STACKempty() && (item = STACKtop()) != '(')
	    { 
	      polonesa[j++] = STACKpop();
	    }

	  STACKpush(infixa[i]);
	  break;
	  
	case '*':
	case '/': 
	  while (!STACKempty() && (item = STACKtop()) != '(' 
		 && item != '+' && item != '-') 
	    {
	      polonesa[j++] = STACKpop();
	    }
	  
	  STACKpush(infixa[i]);
	  break;
	  
	default:  
	  if (infixa[i] != ' ') 
	    polonesa[j++] = infixa[i];
	}

      if (MOSTRE_PILHA) 
	{
	  STACKdump();
	} 

      if (MOSTRE_EXPRESSAO)
	{ 
          int k;  /* usado para imprimir a expressao */

	  fprintf(stdout,"expressao: ");
	  for (k = 0; k < j; k++)
	    {
	      fprintf(stdout, "%c ", polonesa[k]);
	    }
	  fprintf(stdout, "\n");
	}
    }
  
  /* desempilha todos os operandos que restaram */
  while (!STACKempty()) 
    polonesa[j++] = STACKpop();
  
  polonesa[j] = '\0'; /* fim da expressao polonesa */

  STACKfree();
  
  return polonesa;
}  


int 
main(int argc, char *argv[]) 
{  
  if (argc == 1) 
    {
      fprintf(stdout,"Uso: %s \"<expressao infixa>\"\n", 
	      argv[0]);
      return 0;
    }
  
  printf("polonesa: %s\n", para_polonesa(argv[1]));

  return 0;
}



/* STACK.c: IMPLEMENTACAO DA PILHA */

/*
#include <stdlib.h>
#include "Item.h"
#include "STACK.h"
*/

void *
emalloc (unsigned int n)
{
  void *p;

  p = malloc(n);
  if (p == NULL)
    { 
      fprintf(stderr,"malloc de %u bytes falhou.", n);
      exit (-1);
    }
  return p;
}

/*
 * PILHA: uma implementacao com lista encadeada com cabeca
 */
typedef struct STACKnode* link;
struct STACKnode { 
  Item item; 
  link prox; 
};

link topo;


void 
STACKinit(int maxN)
{ 
  topo = (link) emalloc(sizeof *topo);
  topo->prox = NULL;
}

int 
STACKempty()
{ 
  return topo->prox == NULL; 
}

void 
STACKpush(Item item)
{ 
  link p = (link) emalloc(sizeof *p);
  p->item = item;
  p->prox = topo->prox;
  topo->prox = p;
}

Item 
STACKpop()
{ 
  link p = topo->prox;
  Item item;

  if (p == NULL) /* STACKempty() */
    {
      fprintf(stderr,"Putz, voce nao sabe o que esta fazendo!\n");
      exit(-1);
    }
  /* tudo bem, a pilha nao esta vazia... */
  item = p->item;
  topo->prox = p->prox;
  free(p);
  return item;  
}

Item
STACKtop()
{
  if (topo->prox == NULL) /* STACKempty() */
    {
      fprintf(stderr,"Putz, voce nao sabe o que esta fazendo!\n");
      exit(-1);
    }

  /* tudo bem, a pilha nao esta vazia... */
  return  topo->prox->item;
}

void 
STACKfree()
{
  while (topo != NULL) 
    {
      link p = topo;
      topo = topo->prox;
      free(p);
    }
}


void
STACKdump()
{
  link p = topo->prox;
  fprintf(stdout, "pilha:");
  if (p == NULL) fprintf(stdout, "vazia.");
  while (p != NULL)
    {
      fprintf(stdout," %c", p->item);
      p = p->prox;
    }
  fprintf(stdout,"\n");
}