Estruturas de Dados Intermediário/Pilhas/Notação Polonesa

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

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

   n = strlen (inf);
   posf = mallocX (n * sizeof (char));
   pi = mallocX (n * sizeof (char));
   t = 0;
   pi[t++] = inf[0];                          // empilha '('
   for (j = 0, i = 1; /*X*/ inf[i] != '\0'; ++i) {
      // a pilha está em pi[0..t-1]
      switch (inf[i]) {
         char x;
         case '(': pi[t++] = inf[i];          // empilha
                   break;
         case ')': while (1) {                // desempilha
                      x = pi[--t];
                      if (x == '(') break;
                      posf[j++] = x;
                   }
                   break;
         case '+': 
         case '-': while (1) {
                      x = pi[t-1];
                      if (x == '(') break;
                      --t;                    // desempilha
                      posf[j++] = x;
                   }
                   pi[t++] = inf[i];          // empilha
                   break;
         case '*':
         case '/': while (1) {
                      x = pi[t-1];
                      if (x == '(' || x == '+' || x == '-') 
                         break;
                      --t;
                      posf[j++] = x;
                   }
                   pi[t++] = inf[i];
                   break;
         default:  posf[j++] = inf[i];
      }
   }
   free (pi);
   posf[j] = '\0';      
   return posf;
}