10. Notação posfixa ou polonesa

10. Notação posfixa ou polonesa

10. Notação posfixa ou polonesa

Ao introduzir POO usamos, como exemplo, os tipos Fraction e Complexo para para representar dados numéricos. Na aula anterior introduzimos um novo tipo abstrato de dado conhecido como Pilha. Obviamente uma pilha não é um tipo numérico, mas uma estrutura cujo comportamento nos ajuda a resolver problemas computacionais, assim como uma lista ou fila. A abstração dessas estruturas e seus comportamentos nos permite defini-las por meio de classes e instanciá-las em nossos programas por meio de objetos desse tipo.

Para evidenciar os benefícios que o uso de uma estrutura de dados adequada pode trazer a uma solução computacional, vamos ver como a estrutura pilha pode ser usada para calcular o valor de expressões numéricas como “2 + 3 * 4”.

10.1. Objetivos de aprendizagem

Ao final dessa aula você será capaz de:

  • usar a estrutura de dados Pilha em seus programas;
  • explorar o conceito de Pilha diretamente usando listas em Python;
  • converter expressões infixas em posfixas;
  • explicar a motivação para usar a notação posfixa no cálculo de expressões;
  • calcular o valor de expressões posfixas usando uma Pilha.

10.2. Introdução

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.

Estamos tão acostumados com essa notação e a precedência padrão dos operadores que não precisamos indicar a precedência de forma explícita usando parênteses como em 2 + (3 * 4). Outra regra que também usamos é que, quando temos expressões com operadores de mesma precedência como 2 - 3 - 4, calculamos as expressões na mesma ordem de leitura, ou seja, da esquerda para a direita. Por isso o resultado deve ser calculado como (2 - 3) - 4 ao invés de 2 - (3 - 4). Veja mais alguns exemplos executando o código abaixo. Mas antes de clicar em Run, procure calcular esses valores de cabeça.

Portanto, o resultado das expressões infixas depende de regras de precedência dos operadores que podemos controlar explicitamente usando parênteses. Em caso de dúvida, sempre podemos reescrever uma expressão do tipo A + B * C + D como ((A + (B * C)) + D).

Motivação

Imagine uma função resolve() que recebe uma string contendo uma expressão como 2 + 3 * 4 - 5 e você precisa calcular o resultado numérico dessa expressão (como no Trinket acima), obedecendo as regras de precedência que você já conhece e que acabamos de rever.

Um dos problemas que precisamos resolver é definir uma ordem para aplicar cada operador. Estude os seguintes exemplos e verifique a ordem indicada abaixo de cada operador:

2 + 3       ## expressão infixa
  1         ## ordem dos operadores para calcular o resultado

2 + 3 * 4 - 5      ## expressão infixa
  2   1   3        ## ordem dos operadores para calcular o resultado

(A + B) * D + E / (F + A * D) + C   ## outra expressão infixa
   1    2   6   5    4   3    7     ## ordem para calcular cada operador

(1 + 2) * 3 + 4 / (5 + 6 * 7) + 8   ## outra expressão que deve resultar em 17.085106382978722
   1    2   6   5    4   3    7     ## ordem para calcular cada operador

O que você faria para escrever uma função resolve()?

Antes de prosseguir a leitura, reflita como você implementaria essa função.

10.3. Notação polonesa

Antes de introduzir uma solução, precisamos entender que há outras formas de escrever expressões numéricas e que podem simplificar nosso problema. Por exemplo, e se a gente escrevesse o operador depois dos operandos, como em 2 3 +?

Essa notação é conhecida como notação polonesa (reversa) ou posfixa. Para calcular o valor de uma expressão posfixa como 2 3 +, podemos adotar a seguinte regra:

  • Ao ler a expressão da esquerda para a direita, ao encontrar um operador, calcule o valor da operação usando os dois valores antecedentes. Assim, 2 3 + calculamos como 2 + 3 que equivale ao valor 5.

Vamos dizer que a expressão 2 3 + pode ser reduzida para 5. Dessa forma, uma expressão mais complexa como 2 3 4 * + pode ser, primeiramente, reduzida para 2 12 + que, por sua vez, pode ser reduzida a 14, que é resultado final.

10.3.1. Precedência

Observe que, a partir dessa regra simples de redução de uma expressão posfixa, reduzindo cada operador na ordem em que aparece, não há mais ambiguidade ou dúvida sobre qual operador devemos calcular primeiro. Portanto, não há também necessidade de usar parênteses! Os exemplos abaixo ilustram essas vantagens.

infixa posfixa
2 + 3 * 4 2 3 4 * +
(2 + 3) * 4 2 3 + 4 *
2 * 3 + 4 2 3 * 4 +
2 * (3 + 4) 2 3 4 + *
2 - 3 + 4 2 3 - 4 +
2 - (3 + 4) 2 3 4 + -
2 + 3 - 4 2 3 + 4 -
2 + (3 - 4) 2 3 4 - +

Teste seu conhecimento

Complete a tabela com a versão posfixa das expressões.

infixa posfixa
2 * ( 3 + 4 ) / 5 - 6  
2 + 3 * 4  
( 2 + 3 ) * 4  
2 * ( 3 + 4 ) / 5 - 6  
2 - 1  
10 + 3 * 5 / ( 16 - 4 )  

No exemplo abaixo, resgatamos um exemplo onde mostramos a ordem de aplicação dos operadores em uma expressão infixa para deixar claro como essa ordem se torna explícita, sem o uso de parênteses, na própria expressão posfixa.

(A + B) * D + E / (F + A * D) + C   ## outra expressão infixa
   1    2   6   5    4   3    7     ## ordem para calcular cada operador


A B + D * E F A D * + / + C +       ## expressão posfixa
    1   2         3 4 5 6   7       ## ordem para calcular cada operador

10.4. Algoritmo para calcular o valor de uma expressão posfixa

Para reduzir uma expressão em notação polonesa em um valor, é possível utilizar uma pilha da seguinte maneira:

  • números (operandos) são empilhados
  • operadores desempilham 2 operandos da pilha, calculam e empilham o resultado. A pilha portanto contém apenas números.

A tabela abaixo mostra, passo-a-passo, como cada elemento da expressão é processado por esse algoritmo.

Table 10.1 Exemplo de execução
exp polonesa pilha comentário
2 3 4 * + [] pilha vazia
3 4 * + [2] 2 foi empilhado
4 * + [2, 3] 3 foi empilhado
* + [2, 3, 4] 4 foi empilhado
+ [2, 12] 3 e 4 foram desempilhados e 12 (3 * 4) foi empilhado
[14] 2 e 12 foram desempilhados e 14 (2 + 12)foi empilhado

A tabela abaixo mostra uma expressão um pouco mais complexa.

Table 10.2 Exemplo de execução
exp polonesa pilha comentário
2 3 4 + 5 / * 6 - [] pilha vazia
3 4 + 5 / * 6 - [2] 2 foi empilhado
4 + 5 / * 6 - [2, 3] 3 foi empilhado
+ 5 / * 6 - [2, 3, 4] 4 foi empilhado
5 / * 6 - [2, 7] 3 e 4 foram desempilhados e 7 (3+4) foi empilhado
/ * 6 - [2, 7, 5] 5 foi empilhado
* 6 - [2, 1.4] 7 e 5 foram desempilhados e 1.4 (7/5)foi empilhado
6 - [2.8] 2 e 1.4 foram desempilhados e 2.8 (2*1.4) foi empilhado
- [2.8, 6] 6 foi empilhado
[-3.2] 2.8 e 6 foram desempilhados e -3.2 (2.8-6) foi empilhado

Ao final, caso a expressão polonesa seja válida, a pilha de execução terá apenas um elemento, que corresponde ao resultado da expressão.

10.5. Separando os itens léxicos de uma expressão

Vamos dar uma pausa para analisar os elementos de uma expressão infixa ou posfixa, fornecida na forma de uma string como "12+3*45.6". Antes de calcular o resultado precisamos separar essa string nos elementos (números e operadores) que formam a expressão. Por exemplo, podemos quebrar essa string e colocar os elementos em uma lista como ["12", "+", "3", "*", "45.6" ]. Observe que os elementos da lista continuam sendo strings, mas onde cada um representa um item da expressão, como um número ou operador.

Dizemos que uma expressão é composta de itens léxicos (= tokens). Itens léxicos são palavras simples ou grupos de palavras no léxico (conjunto de palavras) de uma língua. No caso de expressões numéricas, vamos considerar que um item léxico é um número (real ou inteiro), ou um operador, ou algum outro símbolo usado em expressões, como parênteses, colchetes etc. No computador também é conveniente considerar nomes de variáveis como itens léxicos em expressões, para usar seus valores associados no cálculo dessas expressões.

Por exemplo, a expressão

perimetro=2*3.14*raio

é formada pela seguinte lista de itens léxicos ["perimetro", "=", "2", "*", "3.14", "*", "raio"].

Por simplicidade, vamos assumir nessa aula que os itens léxicos nas expressões são separados por espaço. Com essa simplificação, a seguinte função separe() recebe uma string contendo uma expressão e retorna uma lista com a sequência de itens léxicos. Experimente incluir outras expressões para testar a função, só não esqueça da restrição que os itens devem estar separados por espaço.

10.6. Exercícios

  1. Suponha que a string polonesa representa uma expressão aritmética em notação posfixa. Suponha que polonesa não é uma string vazia e contém somente números e os operadores +, -, * e / (todos esses operadores são binários, ou seja, exigem dois operandos).

    Escreva uma função que recebe uma string polonesa e calcula o valor da expressão posfixa.

    DICA: use a função separe().

10.7. Onde estamos e para onde vamos?

Nessa aula continuamos de treinar o uso de pilha para ajudar a resolver o problema de cálculo do resultado de uma expressão em notação posfixa. Vimos que o próprio comportamento da estrutura guia o nosso algoritmo a construir uma solução correta. Testando o estado da pilha podemos, inclusive, encontrar problemas na expressão aritmética.

Na próxima aula vamos introduzir outra estrutura de dados muito utilizada, por exemplo, para resolver problemas de álgebra linear, chamada de array.

10.8. Para saber mais