.. -*- coding: utf-8 -*- 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". 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**. 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. .. .. table:: =============== ========= expressão resultado =============== ========= 2 + 3 * 4 = 14 (2 + 3) * 4 = 20 2 * 3 + 4 = 10 2 * (3 + 4) = 14 2 - 3 + 4 = 3 2 - (3 + 4) = -5 2 + 3 - 4 = 1 2 + (3 - 4) = 1 =============== ========= .. trinket .. raw:: html .. .. code:: python print(f"Expressão: '2 + 3 * 4' Resultado: {2 + 3 * 4}") print(f"Expressão: '( 2 + 3 ) * 4' Resultado: {(2 + 3) * 4}") print(f"Expressão: '2 * 3 + 4' Resultado: {2 * 3 + 4}") print(f"Expressão: '2 * ( 3 + 4 )' Resultado: {2 * ( 3 + 4 )}") print(f"Expressão: '2 - 3 + 4' Resultado: {2 - 3 + 4}") print(f"Expressão: '2 - ( 3 + 4 )' Resultado: {2 - ( 3 + 4 )}") print(f"Expressão: '2 + 3 - 4' Resultado: {2 + 3 - 4}") print(f"Expressão: '2 + ( 3 - 4 )' Resultado: {2 + ( 3 - 4 )}") 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)`. .. admonition:: 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: .. code:: python 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. 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. 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. .. table:: =============== ========= 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 - + =============== ========= .. admonition:: 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 ) ======================== ======================= .. solucoes 2 * ( 3 + 4 ) / 5 - 6 2 3 4 + * 5 / 6 - 2 + 3 * 4 2 3 4 * + ( 2 + 3 ) * 4 2 3 + 4 * 2 * ( 3 + 4 ) / 5 - 6 2 3 4 + * 5 / 6 - 2 - 1 2 1 - 10 + 3 * 5 / ( 16 - 4 ) 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. .. code:: python (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 .. Conversão infixa para posfixa [opcional] ---------------------------------------- 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:: 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:: 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. 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 simplicidade vamos considerar apenas as quatro operações básicas representadas por '+', '-', '*' e '/'. Por exemplo, a expressão .. code:: python 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. .. trinket .. raw:: html .. .. code:: python def main(): testes = ["per = 2 * 3.14 * raio", "( A + B ) * 4"] for t in testes: print(f"para '{t}' >>> {separe(t)}") def separe( exp ): ''' (str) -> list recebe uma expressão exp contendo itens léxicos separados por expaço e retorna uma lista com os itens léxicos da expressão. ''' s = exp.strip() ## remove brancos das extremidades de exp itens = s.split() ## quebra a expressão nos espaços return itens if __name__ == "__main__": main() Exercícios ---------- #. 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()``. .. Cuidado com divisões por zero! .. raw:: html .. .. code:: python # CONSTANTES QUE VOCÊ PODE USAR CASO DESEJAR ADD = '+' SUB = '-' MUL = '*' DIV = '/' def main(): ''' Programa para teste da função polonesa ''' exp = input("Digite uma expressão posfixa: ") print(f"{exp} = {polonesa(exp)}") def polonesa( exp ): ''' (str) -> float calcula o valor de uma expressao polonesa ''' return 0 main() 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*. Para saber mais --------------- * `Pilhas `__ da página do Prof. Paulo Feofilloff, em C. * `O que é uma Pilha? `__. * `O tipo abstrato de dados Pilha `__. * `Implementando uma Pilha em Python `__. .. Laboratório: Calculadora polonesa --------------------------------- Essa é uma atividade avançada mas muito divertida. Ao final desse laborátorio, você vai poder brincar com sua própria calculadora que aceita expressões em notação posfixa.