A notação Polonesa (reversa) ou posfixa foi proposta pelo matemático polonês Jan Lukasiewicz, como uma forma de escrever expressões aritméticas e lógicas sem a necessidade de utilizar parênteses. Posteriormente, ela se mostrou apropriada para a representação dessas expressões em linguagens de programação. Essa notação foi, também, popularizada por ter sido adotada em diversas calculadoras científicas, notadamente as calculadoras da marca HP.
Detalhes a respeito da notação polonesa podem ser encontrados na web, por exemplo na página Polish Notation da Wikipedia e também na página do Prof. Feofiloff sobre pilhas (código na linguagem C).
Na notação usual de expressões aritméticas como em (2+3)/4 os operadores são escritos entre os operandos; por isso, a notação é chamada de infixa. Na notação polonesa, ou posfixa, os operadores são escritos depois dos operandos. Eis alguns exemplos de expressões infixas e correspondentes expressões posfixas (retirados da página do Prof. Feofiloff sobre pilhas:
| infixa | posfixa |
|---|---|
| A+B*C | ABC*+ |
| A*(B+C)/D-E | ABC+*D/E- |
| A+B*(C-D*(E-F)-G*H)-I*3 | ABCDEF-*-GH*-*+I3*- |
| A+B*C/D*E-F | ABC*D/E*+F- |
| A+(B-(C+(D-(E+F)))) | ABCDEF+-+-+ |
| A*(B+(C*(D+(E*(F+G))))) | ABCDEFG+*+*+* |
Nesse exercício-programa, vamos implementar uma calculadora para expressões na notação posfixa. Cada expressão pode conter números, variáveis e os seguintes símbolos (caracteres) correspondentes a um operador de atribuição e 7 operadores aritméticos:
| operação | símbolo |
|---|---|
| atribuição | = |
| exponenciação | ^ |
| resto de divisão | % |
| multiplicação | * |
| divisão | / |
| adição | + |
| subtração | - |
| menos unário | ! |
O operador de atribuição '=', atribui um valor a uma variável. Assim, ele requer dois operandos. O primeiro deve ser uma variável e o segundo pode ser um número ou uma variável com valor e retorna esse valor.
O menos unário, é representado pelo símbolo '!'. Assim, para representarmos -4 na nossa notação posfixa devemos escrever 4 !. Portanto, o menos unário requer apenas um operando, que pode ser um número ou uma variável, e retorna o valor desse operando com o sinal trocado.