Notação infixa para pós-fixa:

A manipulação de expressões matemáticas é um exemplo de aplicação do uso de pilhas. Aqui vamos mostrar a transformação da notação infixa para pós-fixa.
Na notação tradicional (notação infixa) temos que o operador aparece entre os seus dois operandos. Já na notação pós-fixa, também conhecida como notação polonesa inversa, o operador é colocado após os seus dois operandos.

Exemplos:

infixa pós-fixa

a-b ab-

a-b*c abc*-

(a-b)*c ab-c*

a+b*c^d-e abcd^*+e-

a*(b+c)*(d-g)*h abc+*dg-*h*

a*b-c*d^e/f+g*h ab*cde^*f/-gh*+

infixa	pós-fixa
a-b	ab-
a-b*c	abc*-
(a-b)*c	ab-c*
a+b*c^d-e	abcd^*+e-
a(b+c)(d-g)*h	abc+dg-h*
ab-cd^e/f+g*h	abcde^f/-gh*+

Na notação pós-fixa é importante observar que:

Não é necessário parênteses.
A ordem dos operadores na expressão diz a ordem em que eles vão ser executados (da esquerda para a direita).

Nos exemplos acima, podemos observar também que:

Os nomes das variáveis são copiados da entrada infixa para a saída pós-fixa na mesma ordem.
Os operadores esperam até que apareça na entrada um de prioridade menor ou igual.

Observe no exemplo "a+b*c^d-e" que os operadores +,*,^ aparecem na expressão pós-fixa "abcd^*+e-" em ordem inversa. Isso sugere o uso de uma pilha para armazenar os símbolos, visto que em uma pilha o último elemento a entrar é o primeiro a sair (política LIFO). Ou seja, elementos removidos de uma pilha aparecem em ordem invertida em relação a ordem de inserção.

Durante o processo de conversão, os caracteres da expressão infixa são processados da esquerda para a direita. Quando operadores com maior prioridade são vistos, esses são empilhados de modo a ocupar o topo da pilha. Eles devem permanecer na pilha até aparecer na entrada um operador de prioridade menor ou igual. Nesse caso, não há porque postergar a sua execução, e o operador deve ser impresso imediatamente na saída.

Problema:

Faça uma função que recebe uma string contendo uma expressão em notação infixa e que imprime a sua expressão correspondente em notação pós-fixa. Considere os seguintes operadores: '+', '-', '*', '/' e '^'. No caso de operadores de mesmo nível de prioridade, considere a associação à esquerda. A exceção é o operador '^' que deve ser associado a direita.

Resolução:

void In2Pos(char expr[]){
  Pilha p;
  int i = 0;
  char c,t;

  p = CriaPilha();
  Empilha(p, '(');

  do{
    c = expr[i];
    i++;
    if(c >= 'a' && c <= 'z'){
      printf("%c", c);
    }
    else if(c == '('){
      Empilha(p, '(');
    }
    else if(c == ')' || c == '\0'){
      do{
        t = Desempilha(p);
        if(t != '(')
          printf("%c", t);
      }while(t != '(');
    }
    else if(c == '+' || c == '-' || 
            c == '*' || c == '/' ||
            c == '^' ){
      while(1){
        t = Desempilha(p);
        if(Prioridade(c,t)){
          Empilha(p, t);
          Empilha(p, c);
          break;
        }
        else{
          printf("%c", t);
        }
      }
    }
  }while(c != '\0');
  printf("\n");
  LiberaPilha(p);
}

Função auxiliar:

A função acima necessita de uma função auxiliar para realizar a comparação das prioridades dos operadores. A prioridade varia, conforme o símbolo se encontre na entrada ou no topo da pilha, de acordo com a seguinte tabela:

Símbolo Pilha Entrada

^ 3 4

*, / 2 2

+, - 1 1

( 0 4

Símbolo	Pilha	Entrada
^	3	4
*, /	2	2
+, -	1	1
(	0	4

int Prioridade(char c, char t){
  int pc,pt;

  if(c == '^')
    pc = 4;
  else if(c == '*' || c == '/')
    pc = 2;
  else if(c == '+' || c == '-')
    pc = 1;
  else if(c == '(')
    pc = 4;

  if(t == '^')
    pt = 3;
  else if(t == '*' || t == '/')
    pt = 2;
  else if(t == '+' || t == '-')
    pt = 1;
  else if(t == '(')
    pt = 0;

  return (pc > pt);
}

Exemplo de programa principal:

int main(){
  char expr[] = "a*b+c*d^e/f-g*h";
 
  In2Pos(expr);
  return 0;
}