.. -*- coding: utf-8 -*- Pilha ===== Uma pilha é um tipo de dado abstrato muito utilizado em computação. Seu nome é devido a analogia do comportamento dessa estrutura com **pilhas de objetos** no mundo real como, por exemplo, uma pilha de livros. O comportamento dessa estrutura sugere que um novo livro seja colocado no topo, assim como o primeiro livro a ser retirado deve sair do topo também. Objetivos de aprendizagem ------------------------- Ao final dessa aula você será capaz de: * Descrever o comportamento da estrutra de dados **Pilha**; * Criar uma classe **Pilha** usando listas em Python; * Utilizar objetos do tipo **Pilha** para resolver problemas computacionais. .. * Uso de pilhas no cálculo de expressões posfixas Introdução ---------- Uma **pilha** (= *stack*) é uma estrutura linear dinâmica em que todas as operações (inserções, remoções e consultas) são feitas em uma mesma extremidade chamada de **topo** da pilha. Portanto, em uma estrutura do tipo pilha, o último elemento inserido é o primeiro a ser removido ou consultado. Essa estrutura também é conhecida como como LIFO (= *last-in first-out*), como ilustrado abaixo. .. code:: python empilha --->---+ +-->----> desempilha (=push) | | (=pop) V | +-----------+ | vvvvvvvvv | +-----------+ | wwwwwwwww | +-----------+ | zzzzzzzzz | +-----------+ | yyyyyyyyy | +-----------+ | xxxxxxxxx | +-----------+ Apenas para fins de comparação, uma **fila** (= *queue*) é outra estrutura linear dinâmica bastante utilizada em computação e que é conhecida como FIFO (= *first-in first-out*). Novos elementos entram no final da fila, e são removidos do começo da fila. Uma classe Pilha em Python -------------------------- Vamos continuar a exercitar a programa orientada a objetos criando uma classe ``Pilha`` em Python. Essa classe tem comportamento muito parecido com a classe `Stack `__ do livro `https://panda.ime.usp.br/panda/static/pythonds_pt/index.html `__, mas "fala" português. Nossa classe `Pilha` deve possuir um **atributo** de nome `dados`. Esse atributo `dados` deve ser uma lista que armazena os itens da pilha. Esse requisito implica no seguinte construtor da classe ``Pilha``: .. code:: python class Pilha: def __init__(self): self.dados = [] Comportamentos de um objeto do tipo Pilha .......................................... Os comportamentos esperados de um objeto do tipo ``Pilha`` são ilustrados pela seguinte função `testes()`: .. code:: python def testes(): pil = Pilha() ## cria uma Pilha vazia print(f"pil.dados = {pil.dados} --> deve ser a lista vazia []") print(f"pil.vazia() = {pil.vazia()} --> deve ser True") pil.empilhe('todos') pil.empilhe(4) pil.empilhe('paz') # Pilha.topo() apenas pega o valor no topo mas sem desempilher print(f"pil.topo() = {pil.topo()} --> deve ser 'paz'") pil.empilhe(True) print(f"len(pil) = {len(pil)} --> deve ser 4") ## implemente o método __len__ print(f"pil.vazia() = {pil.vazia()} --> deve ser False") print(f"pil.dados = {pil.dados} --> deve ser ['todos', 4, 'paz', True]") pil.empilhe(2.7) print(f"pil.desempilhe() = {pil.desempilhe()} --> deve ser 2.7") print(f"pil.desempilhe() = {pil.desempilhe()} --> deve ser True") print(f"len(pil) = {len(pil)} --> deve ser 3") print(f"pil.dados = {pil.dados} --> deve ser ['todos', 4, 'paz']") Estudando os comportamentos esperados pela função `testes()` podemos inferir que a classe deve possuir os seguintes métodos: * ``vazia()``: retorna `True` quando a pilha estiver vazia e `False` caso contrário. * ``empilhe()``: empilha um objeto na pilha. * ``desempilhe()``: retorna o valor do topo da pilha e o remove da pilha. * ``topo()``: retorna o valor no topo da pilha, mas sem desempilhar. Além disso, a função ``len()`` retorna o tamanho da pilha (seu número de elementos). Lembre-se que a função ``len()`` também é usada para listas e strings. Embora possamos definir uma função ``def len()`` fora da classe ``Pilha``, essa redefinição de ``len()`` não é recomendada pois, dentro do nosso programa, essa função deixaria de funcionar para objetos do tipo ``list`` e ``str``. Para estender o comportamento de ``len()`` para o tipo ``Pilha`` sem perder os demais casos nativos da função nativa ``len()``, devemos implementar o método especial ``__len__(self)`` dentro da classe ``Pilha``. A seguinte implementação da classe ``Pilha`` inclui esse e os demais métodos. .. code:: python class Pilha: def __init__(self): '''(Pilha) -> None Monta um objeto da classe Pilha. ''' self.dados = [] def __len__(self): '''(Pilha) -> int Recebe uma Pilha referenciada por self e retorna o número de itens na pilha. Usado pelo Python quando escrevemos len(Pilha). ''' return len(self.dados) def vazia(self): '''(Pilha) -> bool Recebe uma Pilha referenciada por self e retorna True se ela está vazia e False em caso contrário. ''' return self.dados == [] def empilhe(self, item): '''(Pilha, objeto) -> None Recebe uma Pilha referenciada por self e um objeto item e coloca item no topo da pilha. ''' self.dados.append(item) def desempilhe(self): '''(Pilha) -> objeto Recebe uma Pilha referenciada por self e desempilha e retorna o objeto no topo da pilha. ''' return self.dados.pop() def topo(self): '''(Pilha) -> objeto Recebe uma Pilha referenciada por self e retorna o objeto no topo da pilha. O objeto não é removido da pilha. ''' return self.dados[-1] Simule o comportamento dessa classe executando passo-a-passo os testes definidos pela função ``testes()``, clicando no botão ``Forward >``. .. raw:: html .. cscircles def testes(): pil = Pilha() ## cria uma Pilha vazia print(f"pil.dados = {pil.dados} --> deve ser a lista vazia []") print(f"pil.vazia() = {pil.vazia()} --> deve ser True") pil.empilhe('todos') pil.empilhe(4) pil.empilhe('paz') # Pilha.topo() apenas pega o valor no topo mas sem desempilher print(f"pil.topo() = {pil.topo()} --> deve ser 'paz'") pil.empilhe(True) print(f"len(pil) = {len(pil)} --> deve ser 4") ## implemente o método __len__ print(f"pil.vazia() = {pil.vazia()} --> deve ser False") print(f"pil.dados = {pil.dados} --> deve ser ['todos', 4, 'paz', True]") pil.empilhe(2.7) print(f"pil.desempilhe() = {pil.desempilhe()} --> deve ser 2.7") print(f"pil.desempilhe() = {pil.desempilhe()} --> deve ser True") print(f"len(pil) = {len(pil)} --> deve ser 3") print(f"pil.dados = {pil.dados} --> deve ser ['todos', 4, 'paz']") class Pilha: def __init__(self): self.dados = [] def __len__(self): return len(self.dados) def vazia(self): return self.dados == [] def empilhe(self, item): self.dados.append(item) def desempilhe(self): return self.dados.pop() def topo(self): return self.dados[-1] if __name__ == '__main__': testes() .. Você pode estender esses comportamentos, desde que sejam consistentes e não alterem os resultados como ilustrados nos exemplos de testes da `main()`. Exercícios ---------- 1. função `palindromo()` Palíndromo é uma palavra, frase ou número que permanece igual quando lida de trás para diante. Por extensão, palíndromo é qualquer série de elementos com simetria linear, ou seja, que apresenta a mesma sequência de unidades nos dois sentidos [`veja mais a respeito na Wikipedia `__ ]. Na janela do Trinket abaixo, escreva a função `palindromo()` que recebe uma string e retorna `True` caso a string seja um palíndromo, e retorna `False` caso contrário. Sua solução para a função `palindromo()` deve utilizar a sua classe `Pilha`. Observe que uma sequência de empilhamentos seguido por uma sequência de desempilhamentos é uma forma de inverter uma sequência. Por exemplo a sequência de caracteres "pilha" pode ser empilhada, caractere a caractere e, ao ser desempilhada, forma a sequência "ahlip". .. raw:: html .. trinket TESTE = ['ahlip', 'ala', 'sala', 'salas', 'socorrammesubinoonibusemmarrocos'] ESPERADO = [False, True, False, True, True] def testes(): n = len(TESTE) for t in range( n ): s = TESTE[t] r = ESPERADO[t] print(f'{s}: devolveu {palindromo(s)} e deve ser {r}') def palindromo( s ): ''' (str) -> bool Verifica se a string s é palíndromo. Dica: use uma pilha para inverter s. ''' return False class Pilha: def __init__(self): self.dados = [] def __len__(self): return len(self.dados) def vazia(self): return self.dados == [] def empilhe(self, item): self.dados.append(item) def desempilhe(self): return self.dados.pop() def topo(self): return self.dados[-1] if __name__ == '__main__': testes() 2. função `bem_formada()` Uma pilha pode ser utilizada para verificar se uma expressão aritmética contendo uma sequência de parênteses e colchetes está bem formada, ou seja, se todo parênteses e colchetes que abre é fechado na sequência correta. Por exemplo, a sequência "()[] ([])" é bem formada, enquanto as sequências "([)]", "()(" e "]()[" não são bem formadas. Observe que, em Python, ao invés de criarmos a classe ``Pilha``, podemos usar uma lista diretamente, mas tratando a lista como pilha, ou seja, sempre tratando o final da lista como o topo da pilha. Assim, usando os métodos `append()` e `pop()` de listas mas tratando a lista como pilha, escreva uma função ``bem_formada()`` que recebe uma string `s` contendo apenas os caracteres '(', ')' e devolve `True`` caso a expressão estiver bem formada e `False` caso contrário. Dica: a idéia é empilhar todo caractere '(' ou '[' (abre parênteses e abre colchetes) e, ao encontrar um fecha parênteses ou colchetes, verificar se o caractere no topo da pilha "casa" com esse caractere que fecha. Se houver casamento o processo continua, caso contrário o processo pode ser interrompido. Ao final, a pilha precisa estar vazia. **Simule esse processo desenhando o que acontece com a pilha usando apenas papel e lápis com algumas sequências bem e mal formadas antes de tentar escrever seu código em Python**. Onde estamos e para onde vamos? ------------------------------- O tipo ``Pilha`` (= *stack*) é uma estrutura utilizada na solução de vários problemas computacionais. Vimos que criar uma classe ``Pilha`` é muito simples usando uma lista (tipo ``list`` do Python) para representar os dados da pilha. Na verdade, essa implementação é tão simples que podemos usar uma lista diretamente, apenas impondo a inserção e remoção de elementos sempre do "topo", como se a lista fosse uma pilha. Na próxima aula vamos ilustrar o uso de pilhas no cálculo de expressões em notação reversa (= posfixa). 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 `__. .. atividade * palindromo * bem_formada