Projeto de Algoritmos | Índice Remissivo

Código de infixaParaPosfixa que manipula a pilha diretamente

A funçao infixaParaPosfixa poderia operar a pilha diretamente (sem invocar as funções de manipulação da pilha).  Nesse caso, faz mais sentido que as variáveis pilha e t sejam locais:

// A função abaixo recebe uma expressão infixa inf e
// devolve a correspondente expressão posfixa.

char *infixaParaPosfixa (char inf[]) {
   char *posf; 
   char *pilha; int t;
   int N, i, j;

   N = strlen (inf);
   posf = malloc ((N+1) * sizeof (char));
   pilha = malloc (N * sizeof (char));
   t = 0;
   pilha[t++] = inf[0];
   for (j = 0, i = 1; inf[i] != '\0'; ++i) {
      // pilha[0..t-1] é uma pilha de bytes
      switch (inf[i]) {
         char x;
         case '(': pilha[t++] = inf[i];
                   break;
         case ')': while ((x = pilha[--t]) != '(')   
                      posf[j++] = x;
                   break;
         case '+': 
         case '-': while ((x = pilha[t-1]) != '(') { 
                      posf[j++] = x;
                      --t;
                   }
                   pilha[t++] = inf[i];
                   break;
         case '*':
         case '/': while ((x = pilha[t-1]) != '(' 
                          && x != '+' && x != '-') { 
                      posf[j++] = x;
                      --t;
                   }
                   pilha[t++] = inf[i];
                   break;
         default:  posf[j++] = inf[i];
      }
   }
   free (pilha);
   posf[j] = '\0';      
   return posf;
}  

O while nos cases ')', '-' e '/' implementa um n-and-a-half loop.