Notação Polonesa Inversa (ou RPN na sigla em inglês, de Reverse Polish Notation), também conhecida como notação pós-fixada, foi inventada pelo filósofo e cientista da computaçãoaustralianoCharles Hamblin em meados dos anos 1950, para habilitar armazenamento de memória de endereço zero. Ela deriva da notação polonesa, introduzida em 1920 pelo matemáticopolonêsJan Łukasiewicz. (Daí o nome sugerido de notação Zciweisakul.) Hamblin apresentou seu trabalho numa conferência em Junho de 1957, e o publicou em 1957 e 1962.
Conquanto rejeitado em primeira apreciação por parte da maioria dos utilizadores, sob a alegação de ser "muito difícil, preferindo-se a convencional", tudo não passa de apenas uma primeira impressão de quem não tem familiaridade com a nova notação e, pois, com as suas vantagens. Quer na computação automatizada, quer no cálculo manual assistido por instrumentos de cálculo (calculadoras, lato sensu), a notação polonesa reversa (RPN) apresenta as seguintes vantagens:
Reduz o número de passos lógicos para se perfazerem operações binárias e, posto que as demais operações são ou binárias puras compostas, ou binárias compostas com unitárias ou apenas unitárias, o número total de passos lógicos necessários a um determinado cômputo será sempre menor que aquele que utiliza a sintaxe convencional (lógica algébrica direta);
Trabalha com pares ordenadosa priori, somente definindo a lei de composição binária aplicável após a eleição e a introdução do desejado par no cenário de cálculo. Até o momento final, se poderá decidir pela troca ou pela permanência da operação original.
Minimiza os erros de computação, automática ou manual assistida;
Maximiza a velocidade operacional na solução de problemas.
Tudo isso pode ser facilmente constatado na tabela a seguir, por meio de contagem de números de passos lógicos operacionais para o modo RPN comparado com o modo convencional.
A notação RPN tem larga utilização no mundo científico pela fama de permitir uma linha de raciocínio mais direta durante a formulação e por dispensar o uso de parênteses mas mesmo assim manter a ordem de resolução.
Esta notação ganhou ampla notoriedade ao ser adotada pelas calculadoras HP.[1][2][3]
A notação polonesa inversa é utilizada em linguagens de programação de pilhas de dados, como Forth.[4]
Tomemos, como exemplo, a seguinte expressão:
5 + ((1 + 2) × 4) - 3
Esta expressão pode ser representada em notação polonesa inversa como:
5 1 2 + 4 × + 3 −
Lendo a notação da esquerda para a direita, os passos para calculá-la são os seguintes:
Leia um caractere da notação.
Se for um operando, empilhe-o, isto é, coloque-o no topo da pilha.
Mas se ele for um operador, retire o penúltimo e o último operando da pilha. Faça a operação que se pede entre eles e coloque o resultado de volta na pilha.
Repita todos os passos acima até que toda a notação seja lida.
O resultado será o que sobrou na pilha.
A tabela abaixo demonstra os passos para se calcular a expressão anterior. Observa-se que, devido a lógica da notação polonesa inversa, ela dispensa a utilização de parênteses.
Notação
Operação a ser realizada
Pilha
Descrição
5
Colocar 5 na pilha
5
1
Colocar 1 na pilha
5
1
2
Colocar 2 na pilha
5
1
2
+
Soma
5
3
Pegue os dois últimos valores da pilha (1, 2), faça 1 + 2 e coloque o resultado (3) de volta na pilha.
4
Colocar 4 na pilha
5
3
4
×
Multiplicação
5
12
Pegue os dois últimos valores da pilha (3, 4), faça 3 × 4 e coloque o resultado (12) de volta na pilha.
+
Soma
17
Pegue os dois últimos valores da pilha (5, 12), faça 5 + 12 e coloque o resultado (17) de volta na pilha.
3
Colocar 3 na pilha
17
3
-
Subtração
14
Pegue os dois últimos valores da pilha (17, 3), faça 17 - 3 e coloque o resultado (14) de volta na pilha.
Fim
Tomar o resultado
14
A notação foi lida por completo. O resultado é o que sobrou na pilha (14).