{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Orientação a objetos\n", "\n", "A orientação a objetos se baseia no conceito de *tipos abstratos de dados:* queremos definir os tipos através do conjunto de operações permitidas nesses tipos (e não da forma como os dados do tipo são representados no computador).\n", "\n", "Para isso, ao definir um tipo (denominado neste caso uma *classe*), devemos especificar as operações (denominadas *métodos*) que definem esse tipo.\n", "\n", "Por exemplo, no código abaixo definimos um novo tipo (classe) para representar políticos, com um método que diz a promessa de campanha e um método que diz o que é executado quando eleito." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true }, "outputs": [], "source": [ "class Politico:\n", " def promete(self):\n", " print('Vou cuidar dos pobres.')\n", " def executa(self):\n", " print('Envie este dinheiro para a minha firma do Panamá.')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "O uso de `self` será discutido mais adiante." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Quando queremos lidar com esse tipo de elemento, devemos criar um objeto, o que é possível usando a classe como se fosse uma função.\n", "\n", "O resultado é a criação de um *objeto* (uma *instância* da classe)." ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": true }, "outputs": [], "source": [ "juca = Politico()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Agora `juca` é uma variável com uma referência para um objeto da classe `Politico`." ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "<__main__.Politico at 0x7f91ac133240>" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "juca" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Outra forma de dizer é que `Politico` é o tipo do objeto referenciado por `juca`." ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": true }, "outputs": [], "source": [ "a = 1" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "int" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type(a)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "__main__.Politico" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type(juca)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Os métodos da classe podem ser executados sobre um objeto usando a notação `objeto.metodo()`." ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Vou cuidar dos pobres.\n" ] } ], "source": [ "juca.promete()" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Envie este dinheiro para a minha firma do Panamá.\n" ] } ], "source": [ "juca.executa()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Apesar do conjunto de métodos ser uma característica importante da classe, isso não significa que outras classes não possam ter os mesmos métodos.\n", "\n", "Por exemplo, abaixo definimos que religiosos também prometem e executam." ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": true }, "outputs": [], "source": [ "class Religioso:\n", " def promete(self):\n", " print('Vou salvar sua alma')\n", " def executa(self):\n", " print('Vamos construir um templo suntuoso.')" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": true }, "outputs": [], "source": [ "edir = Religioso()" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Vou salvar sua alma\n" ] } ], "source": [ "edir.promete()" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Vamos construir um templo suntuoso.\n" ] } ], "source": [ "edir.executa()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A possibilidade de classes distintas implementarem os mesmos métodos funciona muito bem em conjunto com o fato de que o Python não se importa com o tipo do objeto passado para uma função, desde que ele aceite as operações realizadas dentro da função.\n", "\n", "Por exemplo, a função `promessas` abaixo recebe uma lista e executa o método `promete` em cada elemento da lista. Isso significa que podemos passar uma lista mista com objetos dos tipos `Politico` e `Religioso`." ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def promessas(lista):\n", " for individuo in lista:\n", " individuo.promete()" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "collapsed": true }, "outputs": [], "source": [ "a = [edir, Politico(), juca, Politico(), Religioso(), Politico(), Religioso()]" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[<__main__.Religioso at 0x7f91ac133b70>,\n", " <__main__.Politico at 0x7f91ac13e4e0>,\n", " <__main__.Politico at 0x7f91ac133240>,\n", " <__main__.Politico at 0x7f91ac13e518>,\n", " <__main__.Religioso at 0x7f91ac13e550>,\n", " <__main__.Politico at 0x7f91ac13e588>,\n", " <__main__.Religioso at 0x7f91ac13e5c0>]" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a" ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Vou salvar sua alma\n", "Vou cuidar dos pobres.\n", "Vou cuidar dos pobres.\n", "Vou cuidar dos pobres.\n", "Vou salvar sua alma\n", "Vou cuidar dos pobres.\n", "Vou salvar sua alma\n" ] } ], "source": [ "promessas(a)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Similar ocorre na função `realizado` abaixo." ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def realizado(lista):\n", " for ind in lista:\n", " ind.executa()" ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Vamos construir um templo suntuoso.\n", "Envie este dinheiro para a minha firma do Panamá.\n", "Envie este dinheiro para a minha firma do Panamá.\n", "Envie este dinheiro para a minha firma do Panamá.\n", "Vamos construir um templo suntuoso.\n", "Envie este dinheiro para a minha firma do Panamá.\n", "Vamos construir um templo suntuoso.\n" ] } ], "source": [ "realizado(a)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Se algum dos objetos da lista não entende o método, então teremos um erro durante a execução." ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Envie este dinheiro para a minha firma do Panamá.\n", "Vamos construir um templo suntuoso.\n" ] }, { "ename": "AttributeError", "evalue": "'int' object has no attribute 'executa'", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mAttributeError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mrealizado\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mjuca\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0medir\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m12\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;32m\u001b[0m in \u001b[0;36mrealizado\u001b[0;34m(lista)\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mrealizado\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlista\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mind\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mlista\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0mind\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mexecuta\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;31mAttributeError\u001b[0m: 'int' object has no attribute 'executa'" ] } ], "source": [ "realizado([juca, edir, 12])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exemplo\n", "\n", "Para exemplificar a forma de uso de classes, vamos definir uma estrutura de dados para guardar um *buffer* circular. Este é um *buffer* que permite armazenar até um número máximo (especificado na criação) de elementos. Ao retirar um elemento, retiramos o mais antigo (inserido há mais tempo) que ainda está no *buffer*; ao inserir um elemento, se há espaço, colocamos o elemento após o último, se não há espaço, então o mais antigo elemento é descartado antes da inserção.\n", "\n", "Para implementar, usaremos uma lista com espaço para o número máximo de elementos, um variável indicando o índice nessa lista do próximo elemento a retirar e uma variável dizendo o número de elementos correntemente no buffer. Os elementos serão armazenados \"circularmente\" na lista, começando no próximo a retirar e considerando que o primeiro elemento da lista (de índice 0) é posterior ao último.\n", "\n", "Por exemplo, suponha um *buffer* com espaço para 10 elementos, e que no momento tem 7 elementos armazenados, começando no índice 5. Representando um elemento armazenado por `O` e um elemento livre por `X`, a lista estaria com a seguinte configuração:\n", "\n", " O O X X X O O O O O\n", " \n", "Após a retirada de um elemento, a configuração passaria a ser:\n", "\n", " O O X X X X O O O O\n", " \n", "E se depois inserirmos mais dois elementos teremos:\n", "\n", " O O O O X X O O O O\n" ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "collapsed": true }, "outputs": [], "source": [ "class BufferCircular:\n", " # O método __init__ será discutido abaixo\n", " def __init__(self, tamanho):\n", " self.__buffer = [None for i in range(tamanho)] # Esta é a lista para guardar os valores\n", " self.__n = 0 # __n é o número de valores no buffer\n", " self.__tamanho_buffer = tamanho # __tamanho_buffer é o máximo aceito de elementos\n", " self.__ponto_leitura = 0 # __ponto_leitura é índice do primeiro ocupado na lista\n", " \n", " # Método para inserir um elemento na lista\n", " def coloca(self, valor):\n", " # O ponto de inserção é o ponto de leitura + número de elemento (calculado circularmente)\n", " insercao = (self.__ponto_leitura + self.__n) % self.__tamanho_buffer\n", " # Coloca o valor no ponto de inserção\n", " self.__buffer[insercao] = valor\n", " if self.__n < self.__tamanho_buffer:\n", " # Se havia espaço, incrementa número de elementos no buffer\n", " self.__n += 1\n", " else:\n", " # Se não havia espaço, então foi inserido no antigo primeiro. Atualiza primeiro.\n", " self.__ponto_leitura = (self.__ponto_leitura + 1) % self.__tamanho_buffer\n", " \n", " # Método para retirar objeto do buffer\n", " def retira(self):\n", " # Se buffer está vazio, é um erro.\n", " if self.__n == 0:\n", " raise Exception('Tentativa de retirada de buffer vazio')\n", " # Se tinha algo, atualiza ponto de leitura para o próximo e decrementa número de elementos no buffer.\n", " self.__ponto_leitura = (self.__ponto_leitura + 1) % self.__tamanho_buffer\n", " self.__n -= 1\n", " \n", " # Método para ler o valor do próximo objeto a retirar.\n", " def valor(self):\n", " # Se está vazio, o valor não existe.\n", " if self.__n == 0:\n", " raise Exception('Tentativa de leitura em buffer vazio')\n", " # Se há elementos, simplesmente retorna o apontado pelo ponto de leitura.\n", " return self.__buffer[self.__ponto_leitura]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Quando criamos um objeto da classe, o método `__init__` é chamado, e os parâmetros passados durante a criação são passados para esse método. Por exemplo, no código abaixo é criado um objeto do tipo `BufferCircular` e em seguida o método `__init__` é chamado com o valor 5 passado para o parâmetro `tamanho`." ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "collapsed": true }, "outputs": [], "source": [ "b = BufferCircular(5)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Você deve ter reparado que os códigos dos métodos fazem amplo uso de `self`. Os métodos de uma classe (exceções serão discutidas em outra aula) devem ter como primeiro parâmetro o `self`. Esse parâmetro será uma variável com uma referência para o objeto sobre o qual o método foi chamado (isto é, o objeto que está à esquerda do ponto na chamada do método).\n", "\n", "Com o uso de `self`, podemos definir variáveis internas ao objeto, que poderão ser acessadas através dele pelos métodos da classe ou diretamente. Cada objeto da classe terá uma cópia própria dessas variáveis.\n", "\n", "Vamos agora fazer alguns testes na classe.\n", "\n", "Em primeiro lugar, não é possível ler valor de um buffer vazio." ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "collapsed": false }, "outputs": [ { "ename": "Exception", "evalue": "Tentativa de leitura em buffer vazio", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mException\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mb\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mvalor\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;32m\u001b[0m in \u001b[0;36mvalor\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m 33\u001b[0m \u001b[0;31m# Se está vazio, o valor não existe.\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 34\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m__n\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 35\u001b[0;31m \u001b[0;32mraise\u001b[0m \u001b[0mException\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'Tentativa de leitura em buffer vazio'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 36\u001b[0m \u001b[0;31m# Se há elementos, simplesmente retorna o apontado pelo ponto de leitura.\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 37\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m__buffer\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m__ponto_leitura\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;31mException\u001b[0m: Tentativa de leitura em buffer vazio" ] } ], "source": [ "b.valor()" ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "collapsed": true }, "outputs": [], "source": [ "b.coloca(1)" ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "collapsed": true }, "outputs": [], "source": [ "b.coloca(2)" ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "collapsed": true }, "outputs": [], "source": [ "b.coloca(3)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Agora o buffer circular `b` tem os valores\n", "\n", " 1 2 3" ] }, { "cell_type": "code", "execution_count": 28, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "b.valor()" ] }, { "cell_type": "code", "execution_count": 29, "metadata": { "collapsed": true }, "outputs": [], "source": [ "b.retira()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ficamos agora com\n", "\n", " 2 3" ] }, { "cell_type": "code", "execution_count": 30, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "b.valor()" ] }, { "cell_type": "code", "execution_count": 31, "metadata": { "collapsed": true }, "outputs": [], "source": [ "b.coloca(4)" ] }, { "cell_type": "code", "execution_count": 32, "metadata": { "collapsed": true }, "outputs": [], "source": [ "b.coloca(5)" ] }, { "cell_type": "code", "execution_count": 33, "metadata": { "collapsed": true }, "outputs": [], "source": [ "b.coloca(6)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "E agora temos\n", "\n", " 2 3 4 5 6" ] }, { "cell_type": "code", "execution_count": 34, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "b.valor()" ] }, { "cell_type": "code", "execution_count": 35, "metadata": { "collapsed": true }, "outputs": [], "source": [ "b.coloca(7)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "O 7 não cabe, então o mais antigo (2) é jogado fora:\n", "\n", " 3 4 5 6 7" ] }, { "cell_type": "code", "execution_count": 36, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "3" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "b.valor()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Os atributos criados nos objetos com nomes precedidos por `__` são considerados \"privados\" ao objeto, e devem ser acessados apenas pelos métodos da própria classe." ] }, { "cell_type": "code", "execution_count": 37, "metadata": { "collapsed": false }, "outputs": [ { "ename": "AttributeError", "evalue": "'BufferCircular' object has no attribute '__n'", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mAttributeError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mb\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m__n\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;31mAttributeError\u001b[0m: 'BufferCircular' object has no attribute '__n'" ] } ], "source": [ "b.__n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Na verdade, como eles fazem parte do dicionário associado ao objeto, podemos acessá-los se soubermos construir o nome apropriado, mas isso não deve ser feito." ] }, { "cell_type": "code", "execution_count": 38, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "{'_BufferCircular__buffer': [6, 7, 3, 4, 5],\n", " '_BufferCircular__n': 5,\n", " '_BufferCircular__ponto_leitura': 2,\n", " '_BufferCircular__tamanho_buffer': 5}" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "b.__dict__" ] }, { "cell_type": "code", "execution_count": 39, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "5" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "b._BufferCircular__n" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "## Exemplo: Árvore binária" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Implementar uma classe para nós de uma árvore binária e com métodos para percorrer a árvore das formas tradicionais." ] }, { "cell_type": "code", "execution_count": 41, "metadata": { "collapsed": false }, "outputs": [], "source": [ "class Nodo:\n", " # Incializamos um nodo guardando o valor e marcando os filhos\n", " # da esquerda e da direita vazios.\n", " def __init__(self, valor):\n", " self.__valor = valor\n", " self.__esquerda = None\n", " self.__direita = None\n", " \n", " # Inserir o nodo passado como filho da esquerda\n", " def coloca_esquerda(self, nodo):\n", " self.__esquerda = nodo\n", " \n", " # Inserir o nodo passado como filho da direita\n", " def coloca_direita(self, nodo):\n", " self.__direita = nodo\n", " \n", " # Ler o valor armazenado no nodo corrente\n", " def valor(self):\n", " return self.__valor\n", " \n", " # Retornar o filho da esquerda\n", " def esquerda(self):\n", " return self.__esquerda\n", " \n", " # Retornar o filho da direita\n", " def direita(self):\n", " return self.__direita\n", " \n", " # Percorrer a árvore em profundidade, pré-ordem, partindo do\n", " # nodo corrente.\n", " def percorre_pre_ordem(self, f):\n", " f(self.__valor)\n", " if self.__esquerda: self.__esquerda.percorre_pre_ordem(f)\n", " if self.__direita: self.__direita.percorre_pre_ordem(f)\n", " \n", " # Percorrer a árvore em profundidade, pós-ordem, partindo do\n", " # nodo corrente\n", " def percorre_in_ordem(self, f):\n", " if self.__esquerda: self.__esquerda.percorre_in_ordem(f)\n", " f(self.__valor)\n", " if self.__direita: self.__direita.percorre_in_ordem(f)\n", " \n", " # Percorrer a árvore em profundidade, in-ordem, partindo do\n", " # nodo corrente\n", " def percorre_pos_ordem(self, f):\n", " if self.__esquerda: self.__esquerda.percorre_pos_ordem(f)\n", " if self.__direita: self.__direita.percorre_pos_ordem(f)\n", " f(self.__valor)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Código de teste. Criando uma árvore." ] }, { "cell_type": "code", "execution_count": 42, "metadata": { "collapsed": false }, "outputs": [], "source": [ "aux1 = Nodo(2)\n", "aux1.coloca_esquerda(Nodo(3))\n", "aux2 = Nodo(7)\n", "aux2.coloca_esquerda(Nodo(10))\n", "aux2.coloca_direita(Nodo(11))\n", "aux3 = Nodo(1)\n", "aux3.coloca_esquerda(aux1)\n", "aux3.coloca_direita(aux2)\n", "aux1 = Nodo(4)\n", "aux1.coloca_esquerda(Nodo(9))\n", "aux1.coloca_direita(Nodo(8))\n", "raiz = Nodo(5)\n", "raiz.coloca_esquerda(aux3)\n", "raiz.coloca_direita(aux1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Verificando a árvore:" ] }, { "cell_type": "code", "execution_count": 43, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[5, 1, 4, 2, 7, 9, 8, 3, None, 10, 11]" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[raiz.valor(), raiz.esquerda().valor(), raiz.direita().valor(), \n", " raiz.esquerda().esquerda().valor(), raiz.esquerda().direita().valor(),\n", " raiz.direita().esquerda().valor(), raiz.direita().direita().valor(),\n", " raiz.esquerda().esquerda().esquerda().valor(), raiz.esquerda().esquerda().direita(),\n", " raiz.esquerda().direita().esquerda().valor(), raiz.esquerda().direita().direita().valor()]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Agora vamos percorrer a árvore." ] }, { "cell_type": "code", "execution_count": 44, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Pre ordem: [5, 1, 2, 3, 7, 10, 11, 4, 9, 8]\n", "In ordem: [3, 2, 1, 10, 7, 11, 5, 9, 4, 8]\n", "Pos ordem: [3, 2, 10, 11, 7, 1, 9, 8, 4, 5]\n" ] } ], "source": [ "nodos = []\n", "raiz.percorre_pre_ordem(lambda x: nodos.append(x))\n", "print('Pre ordem:', nodos)\n", "nodos = []\n", "raiz.percorre_in_ordem(lambda x: nodos.append(x))\n", "print('In ordem:', nodos)\n", "nodos = []\n", "raiz.percorre_pos_ordem(lambda x: nodos.append(x))\n", "print('Pos ordem:', nodos)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Alguns outros exemplos simples" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Vamos definir um tipo de objetos (classe) que são responsáveis por fazer contagem de quantas vezes algo aconteceu. Os objetos guardam o número de ocorrência e têm um método (`mais_um`) para indicar uma nova ocorrência e um método `valor` para verificar quantas ocorrências houveram até o momento da chamada. O objeto precisa ter seu valor inicializado em zero ao ser criado.\n", "\n", "Traduzido para Python, fica desta forma:" ] }, { "cell_type": "code", "execution_count": 54, "metadata": { "collapsed": true }, "outputs": [], "source": [ "class Contador:\n", " def __init__(self):\n", " self.__valor = 0\n", " def mais_um(self):\n", " self.__valor += 1\n", " def valor(self):\n", " return self.__valor" ] }, { "cell_type": "code", "execution_count": 55, "metadata": { "collapsed": false }, "outputs": [], "source": [ "c1 = Contador()\n", "if c1.valor() != 0: raise Exception('Inicialização errada')" ] }, { "cell_type": "code", "execution_count": 56, "metadata": { "collapsed": false }, "outputs": [], "source": [ "c1.mais_um()\n", "if c1.valor() != 1: raise Exception('Erro no incremento')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Agora vamos fazer uma classe para guardar informações de base e altura de retângulos. Cada objeto representará um retângulo, com valores de base e altura específicos.\n", "\n", "Ao criar o objeto (retângulo) precisamos indicar qual a base e a altura. Após isso, só queremos verificar algumas de suas características geométricas, como perímetro, área, diagnoal, base e altura.\n", "\n", "Tomamos o cuidado de verificar que base e altura não sejam negativos (não faria sentido)." ] }, { "cell_type": "code", "execution_count": 65, "metadata": { "collapsed": true }, "outputs": [], "source": [ "class Retangulo:\n", " def __init__(self, base, altura):\n", " if base < 0: raise Exception('Base precisa ser positiva')\n", " if altura < 0: raise Exception('Altura precisa ser positiva')\n", " self.__base = base\n", " self.__altura = altura\n", " def base(self):\n", " return self.__base\n", " def altura(self):\n", " return self.__altura\n", " def perimetro(self):\n", " return 2*(self.__base + self.__altura)\n", " def area(self):\n", " return self.__base * self.__altura\n", " def diagonal(self):\n", " import math\n", " return math.sqrt(self.__base ** 2 + self.__altura ** 2)" ] }, { "cell_type": "code", "execution_count": 66, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Área 1\n", "Perímero 4\n", "Diagonal 1.4142135623730951\n", "Área 12\n", "Perímero 14\n", "Diagonal 5.0\n", "Área 0.12\n", "Perímero 1.4\n", "Diagonal 0.5\n" ] } ], "source": [ "r1 = Retangulo(1,1)\n", "r2 = Retangulo(3,4)\n", "r3 = Retangulo(0.3, 0.4)\n", "for r in [r1, r2, r3]:\n", " print('Área', r.area())\n", " print('Perímero', r.perimetro())\n", " print('Diagonal', r.diagonal())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Agora vamos definir um tipo um pouco mais útil. Os objetos dessa classe receberão diversos valores, e terâo guardados sempre os dois maiores valores que receberam até o momento (desde a sua criação).\n", "\n", "Para isso, vamos ter duas variáveis locais do objeto (membros) `__a` e `__b`, onde a primeira guardará o maior valor já enviado e a segunda o segundo maior valor. No início, marcaremos essas variáveis com `None` para indicar que não há valor correspondente.\n", "\n", "Temos então um método `recebe` para passar um novo valor ao objeto e um método `maiores`, que retorna os dois maiores valores recebidos em um tupla de dois elementos, com o maior no primeiro elemento." ] }, { "cell_type": "code", "execution_count": 69, "metadata": { "collapsed": true }, "outputs": [], "source": [ "class Dois_maiores:\n", " def __init__(self):\n", " self.__a = None\n", " self.__b = None\n", " def recebe(self, valor):\n", " # Supondo a >= b sempre\n", " if not self.__a:\n", " self.__a = valor\n", " return\n", " if valor >= self.__a:\n", " self.__b = self.__a\n", " self.__a = valor\n", " elif not self.__b or valor > self.__b:\n", " self.__b = valor\n", " def maiores(self):\n", " return self.__a, self.__b" ] }, { "cell_type": "code", "execution_count": 70, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "(None, None)" ] }, "execution_count": 70, "metadata": {}, "output_type": "execute_result" } ], "source": [ "d = Dois_maiores()\n", "d.maiores()" ] }, { "cell_type": "code", "execution_count": 71, "metadata": { "collapsed": true }, "outputs": [], "source": [ "d.recebe(1); d.recebe(-1); d.recebe(10); d.recebe(10); d.recebe(15)" ] }, { "cell_type": "code", "execution_count": 72, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "(15, 10)" ] }, "execution_count": 72, "metadata": {}, "output_type": "execute_result" } ], "source": [ "d.maiores()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "### Sugestão:\n", "\n", "Como exercício, faça o seguinte:\n", "\n", "- Pense em nomes melhores para as variáveis `__a` e `__b`, que façam o código acima ficar auto-explicativo.\n", "- Suponha agora que você quer usar esses objetos de tal forma que, em um dado instante, podemos pedir para o objeto reiniciar, esquecendo tudo o que já tinha recebido, passando a operar como se fosse um novo objeto recém-criado. Vamos chamar esse método de `esquece`. Altere a classe para implementar esse método." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python [default]", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.5.2" } }, "nbformat": 4, "nbformat_minor": 0 }