Notação polonesa inversa
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Disambig_grey.svg/20px-Disambig_grey.svg.png)
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ção australiano Charles 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ático polonês Jan Ł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 ordenados a 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]
Operação | Notação convencional | Notação Polonesa | Notação Polonesa Inversa |
---|---|---|---|
a+b | + a b | a b + | |
(a+b)/c | / + a b c | a b + c / | |
((a*b)-(c*d))/(e*f) | / - * a b * c d * e f | a b * c d * - e f * / |
Cálculo com o auxílio de uma pilha
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). |
Ver também
Referências
- ↑ «RPN: Uma introdução à notação polonesa reversa». Aunimaq. 2015. Consultado em 1 de fevereiro de 2015 [ligação inativa]
- ↑ «Aprendendo a usar a calculadora HP 12C - Editora Atlas». Editora Atlas. Consultado em 1 de fevereiro de 2015. Arquivado do original em 16 de maio de 2014
- ↑ «TUTORIAL 1: Uma visão geral da HP48». Instituto Federal de Ciência e Tecnologia e Educação e São Paulo. Consultado em 15 de junho de 2017
- ↑ http://www.dei.isep.ipp.pt/~luis/stack_machines/cap3.html Resumo da linguagem de programação Forth – Departamento de Engenharia Informática
Ligações externas
- (em português)-Introdução ao RPN em Calculadoras
- (em inglês)-RPN or DAL? A brief analysis of Reverse Polish Notation against Direct Algebraic Logic