Notação posfixa

A notação tradicional para expressões aritméticas, que representa uma operação binária na forma x+y, ou seja, com o operador entre seus dois operandos, é conhecida como notação infixa. Uma notação alternativa para esse tipo de expressão é a notação posfixa, também conhecida como notação polonesa^3.1, na qual o operador é expresso após seus operandos.

O atrativo da notação posfixa é que ela dispensa o uso de parênteses. Por exemplo, as expressões

  a*b+c;
  a*(b+c);
  (a+b)*c;
  (a+b)*(c+d);

seriam representadas nesse tipo de notação respectivamente como

  a b * c +
  a b c + *
  a b + c *
  a b + c d + *

Instruções de desvio em código intermediário usando a notação posfixa assumem a forma

   L jump
   x y L jcc

para desvios incondicionais e condicionais, respectivamente. No caso de um desvio condicional, a condição a ser avaliada envolvendo x e y é expressa na parte cc da própria instrução. Assim, jcc pode ser uma instrução entre jeq (desvio ocorre se x e y forem iguais), jne (se diferentes), jlt (se x menor que y), jle (se x menor ou igual a y), jgt (se x maior que y) ou jge (se x maior ou igual a y).

Expressões em formato intermediário usando a notação posfixa podem ser eficientemente avaliadas em máquinas baseadas em pilhas, também conhecidas como máquinas de zero endereços. Nesse tipo de máquinas, operandos são explicitamente introduzidos e retirados do topo da pilha por instruções push e pop, respectivamente. Além disso, a aplicação de um operador retira do topo da pilha seus operandos e retorna ao topo da pilha o resultado de sua aplicação.

Por exemplo, a avaliação da expressão a*(b+c) em uma máquina baseada em pilha poderia ser traduzida para o código

   push a
   push b
   push c
   add
   mult