domingo, 18 de maio de 2014

[Programação em C++] - Notação polonesa pós-fixa

Olá pessoal, nesse post iremos falar um pouquinho sobre a notação polonesa pós-fixa (reverse polish notation).

Na notação polonesa não temos o uso de parênteses, os operadores aparecem na ordem que devem ser executados.

A expressão por exemplo (x + (y * z)) em notação polonesa pós-fixa é: x y z * +.

A implementação é simples, basta seguir o algoritmo:

a) Ao encontrar um operando (valor), este deve ser empilhado.

b) Ao encontrar um operador, seus operandos devem ser desempilhados, deve ser feita a operação e o resultado deve ser empilhado.

Lembrando que a avaliação da expressão é da esquerda para a direita!

Para implementar iremos utilizar a linguagem C++. Iremos usar diversas funções das mais variadas bibliotecas para tornar mais fácil o trabalho (não reinventar a roda). É o caso por exemplo do uso da biblioteca stack do C++ que já implementa uma pilha.


O código está comentado (em inglês) para simplificar o entendimento.

No código acima, os únicos operadores permitidos são +, -, * ou /. Lembrando que não foi feita a validação para verificar se a entrada do usuário realmente é uma expressão que está na notação polonesa reversa (pós-ordem).

Iremos usar como exemplo de entrada o mesmo exemplo do link do Wikipédia passado acima.

Exemplo de entrada: 1 2 + 4 * 5 + 3 −

Execução:
(clique na imagem para vê-la em tamanho maior)


Então é isso pessoal, não vou explicar o código pois ele está comentado, mas quaisquer dúvidas deixem nos comentários. Até a próxima!


2 comentários:

Anônimo disse...

Muito legal essa implementação.
Você teria algum exemplo de uma calculadora pós-fixa utilizando pilha com vetor ou lista?

abraços,

Paulo

admin disse...

Não tenho amigo, mas posso implementar e em breve disponibilizar. Obrigado pela visita.