18-03-2009: Tenho outro artigo sobre o assunto, caso você esteja procurando como implementar uma calculadora com RPN.
Estava brincando com o galculator no Linux (esse nome é ridículo, mas enfim) e vi que ele possui três modos de entrada: algébrico (mais ou menos como nas calculadoras de 4 funções normais), entrada de fórmulas (em que podemos digitar uma longa expressão de uma vez só, como nas calculadoras científicas da Casio) e notação polonesa reversa.
Essa última me chamou a atenção, me lembrou um pouco Lisp, só que ao contrário, então fui pesquisar mais sobre o assunto.
Basicamente, existem três tipos de notação matemática, com os operadores antes dos números (Lisp), com os operadores no meio dos números (a que estamos acostumados) e com os operadores depois dos números (me parece que algumas calculadoras da HP funcionam desse modo).
Não falarei da notação algébrica já que usamo-na no dia-a-dia. A notação polonesa foi inventada por Jan Łukasiewicz apresenta a vantagem de não ser necessário o uso de parenteses.
+ 2 3
Quer dizer “some 2 com 3”. A leitura dos números na ordem em que eles aparecem é importante, principalmente na divisão, pois poderia gerar confusão.
/ 10 5
Significa “divida 10 por 5” e resulta em 2, não em ½.
Expressões maiores podem parecer confusas no princípio, mas é apenas questão de treino. De uma maneira simples, começa-se a ler da esquerda para a direita e segue-se a seguinte ordem:
- Encontra-se o primeiro operador
- Verifica-se os dois símbolos que o seguem. Se forem dois números, resolve-se-los (que coisa mais estranha =P), se um dos dois símbolos ou ambos forem outros operadores, passa-se ao operador mais a direita.
- Para melhores resultados, repita o procedimento e use condicionador e creme para pentear da PolishNotation Shampoos Ltda.
Aqui está um exemplo:
* + 2 - 9 4 / 6 2
O primeiro operador a ser seguido de dois números é “- 9 4”, então vamos resolvê-lo. (Alternativamente, poderia ser resolvido “/ 6 2” ao mesmo tempo, mas vamos com calma nesse primeiro exemplo)
* + 2 5 / 6 2
Aqui podemos resolver “+ 2 5”:
* 7 / 6 2
E aqui, “/ 6 2”:
* 7 3
21
Note que não há ordem certa para resolver as operações, simplesmente segue-se da esquerda para a direita. Aqui está o código em Lisp apenas para comparação:
(* (+ 2 (- 9 4)) (/ 6 2))
A notação polonesa reversa é basicamente a mesma coisa, só que ao contrário (O RLY? YA RLY). A idéia é deixar os dois números que serão calculados ‘empilhados’ e depois escolhermos a operação.
Digamos que nós temos a seguinte operação:
(8 - 2)*(4 + 3)
Na notação polonesa reversa isso ficaria como:
8 2 - 4 3 + *
A leitura procede da mesma maneira que na notação polonesa normal, mas começando do outro lado. Primeiro resolvemos o operador a ter dois números antes dele e assim sucetivamente:
6 7 *
42 (eu juro que esse 42 foi sem querer)
Sua utilização em calculadoras ocorre da seguinte forma: ao invés de possuir um botão de =, a calculadora terá um botão ‘enter’, que servirá para armazenar números na pilha (pilha de números, não pilha equivalente a bateria). Após armazenados os números, escolhemos a operação e o resultado logo aparece.
A operação que calculamos anteriormente ficaria:
[8] [enter] [2] [-] [4] [enter] [3] [+] [*]
O que nos dá uma vantagem de dois digitos em relação a notação convencional.
Além da ausência de parenteses, a notação polonesa reversa apresenta uma vantagem na hora da implementação do algoritmo e permite a escrita de operações mais complexas com menos dígitos.