Tópicos
Os tipos de dados que você viu até agora são todos concretos, no sentido que nós especificamos completamente como eles são implementados. Por exemplo, a classe Card(XXX ver como foi traduzido) representa uma carta utilizando dois inteiros. Como discutimos no momento, esta não é a única maneira de representar uma carta; existem muitas implementações alternativas.
Um tipo abstrato de dado, ou TAD, especifica um conjunto de operações (ou métodos) e a semântica das operações (o que elas fazem), mas não especifica a implementação das operações. Isto é o que o faz abstrato.
Por que isto é útil?
- Simplifica a tarefa dde especificar um algoritmo se você pode XXXdenotar(denote) as operações que você precisa sem ter que pensar, ao mesmo tempo, como as operações são executadas.
- Uma vez que existem geralmente muitas maneiras de implementar um TAD, pode ser útil escrever um algritmo que pode ser usado com qualquer das possíveis implementações.
- TADs bastante conhecidos, como o TAD Pilha deste capítulo, já estão implementados em bibliotecas padrão, então eles podem ser escritos uma vez e usado por muitos programadores.
- As operações em TADs provêm uma linguagem de alto nível comum para especificar e falar sobre algoritmos.
Quando falamos sobre TADs, geralmente distinguimos o código que usa o TAD, chamado cliente, do código que implementa o TAD, chamado código fornecedor.
Neste capítulo, iremos olhar um TAD comum, a pilha. Uma pilha é uma coleção, ou seja, é uma estrutura de dados que contei múltiplos elementos. Outras coleções que vimos incluem dicionários e listas.
Um TAd é definido pelo conjunto de operações que podem ser executadas nele, que é chamado interface. A interface para uma pilha consiste nestas operações:
__init__ : Inicializa uma nova pilha vazia.
push : Adiciona um novo item na pilha
pop : Remove um ítem da pilha e o retorna, O ítem que é retornadao é sempre o último adicionado.
isEmpty : Verifica se a pilha está vazia.
Uma às vezes é chamada uma estrutura de dados “last in, first out” ou LIFO, porque o último ítem adicionad é o primeiro a ser removido.
As operações de lista que Python oferecem são similares às operações que definem uma pilha. A interface não é exatamente o que se supõe ser, mas podemos escrever um código para traduzir do TAD Pilha para as operações nativas.
Este código é chamado uma implementação do TAD Pilha. Geralmente, uma implementaçõa é um conjunto de métodos que satisfazem os requisitos sintáticos e semânticos de uma interface.
Aqui está uma implementação do TAD Pilha que usa uma lista do Python:
class Stack :
def __init__(self) :
self.items = []
def push(self, item) :
self.items.apend(item)
def pop(self) :
return self.items.pop()
def isEmpty(self) :
return (self.items == [])
Um objeto Stack contém um atributo chamado items que é uma lista de ítens na pilha. O método de inicialização define items como uma lista vazia.
Para adicionar um novo ítem na pilha, push o coloca em items. Para remover um ítem da pilha, pop usa o método de lista homônimo¹ para remover e retornar um último ítem da lista.
Finalmente, para verificar se a pilha está vazia, isEmpty comprara items a uma lista vazia.
Uma implementação como esta, na qual os métodos consistem de simples invocações de métodos existentes, é chamado revestimento. Na vida real, revestimento é uma fina camada de madeira de boa qualidade usado em XXX*furniture-making* para esconder madeira de menor qualidade embaixo. Cientistas da Computação usam esta metáfora para descrever um pequeno trecho de código que esconde os detalhes de uma implementação e fornece uma interface mais simples, ou mais padronizada.
Uma pilha é uma estrutura de dados genérica, o que significa que podemos adicionar qualquer tipo de ítem a ela. O exemplo a seguir empilha dois inteiros e uma XXXstring na pilha:
>>> s = Stack()
>>> s.push(54)
>>> s.push(45)
>>> s.push("+")
Podemos usar isEmpty e pop para remover e imprimir todos os ítens da pilha:
- while not s.isEmpty() :
- priint s.pop()
A saída é + 45 54. Em outras palavras, usamos a pilha para imprimir os ítens ao contrário! Sabidamente, este não é o formato padrão de imprimir uma lista, mas, usando uma pilha, foi notavelmente fácil de fazer.
Você deve comparar este trecho de código com a implementação de printBackward na seção 17.4. Existe um paralelo natura entre a versão recursiva de printBackward e o algoritmo de pilha aqui. A diferenã é que printBackward usa a pilha de execução para XXXmanter a trilha(keep track) dos nós enquanto percorre a lista, e então imprime-a no retorno da recursão. o algoritmo de pilha faz a mesma coisa, exceto que usa o objeto Stack ao invés da pilha de execução.
Em muitas linguagens de programação, expressões matemáticas são executadas com o poerador entre os roid operandos, como em 1 + 2. Este formato é chamado notação infixa. Uma alternativa usada por algumas calculadoras é chamada notação pós-fixa. Em notação pós-fixa, o operador segue os operandos, como em 1 2 +.
A razão pela qual a notação pós-fixa é útil algumas vezes é que existe uma maneira natural de avaliar uma expressão pós-fixa usando uma pilha:
- começando no início da expressão, peque um termo (operador ou operando) de cada vez.
- Se o termo é um operando, empilhe-o
- Se o termo é um operador, desempilhe dois operandos, execute a operação neles, e empilhe o resultado.
- Quando chegar ao fim da expressão, deve existir exatamente um operando sobrando na pilha. Este operando é o resultado.
- Como um exercício, aplique este algoritmo à expressão 1 2 + 3 * .
Este exemplo demonstra uma das vantagens da notação pós-fixa - não é necessário usar parênteses para controlar a ordem das operações. Para ter o mesmo resultado em notação infixa, deveríamos escrever (1 + 2) * 3.
- Como um exercício, escreva a expressão pós-fixa que é equivalente a 1 + 2 * 3.
Para implementar o algoritmo anterior, necessitamos estar prontos para percorrer uma string e quebrá-la em operandos e operadores. Este processó é um exemplo de XXXparsing, e o resultado - os pedaços da string - são chamados XXXtokens. Você deve lembrar estas palavras do capítulo 1.
Python fornece um método split nos módulos string e re (expressões regulares). A função string.split separa uma string numa lista usando um único caracter como delimitador. Por exemplo:
>>> import string
>>> string.split ("Now is the time", " ")
['Now', 'is', 'the', 'time']
Neste caso, o delimitador é o caracter de espaço, então a string é dividida a cada espaço.
A função re.split é mais poderosa, permitindo-nos fornecer uma expresão regular ao invés de um delimitador. Uma expressão regular é uma maneira de especificar um conjunto de strings. Por exemplo, [A-z] é o conjunto de todas as letras e [0-9] é o conjunto de todos os dígitos. O operador ^nega um conunto, então [^0-9] é o conjunto de tudo o que não é número, que é exatamente o que queremos para dividir expressões pós-fixas.
>>> import re
>>> re.split ("[^0-9]", "123+456*/")
['123', '+', '456', '*', '', '/', ' ']
Note que a ordem dos argumentos é diferente de string.split, o delimitador vem antes da string.
A lista resultante inclui os operandos 123 e 456, e os operadores * e /. Também inclui duas strings vazias que são inseridas depois dos operadores.
Para avaliar uma expressão pós-fixa, usaremos o parser da seção anterior e o algoritmo da seção anterior a ela. Para manter as coisas simples, começaremos com um avaliador que implementa somente os operadores + e .
def evalPostfix (expr) :
import re
tokenList = re.split ("([^0-9])", expr)
stack = Stack()
for token in tokenList
if token == '' or token = ' ' :
continue
if token == '+' :
sum = stack.pop() + stack.pop()
stack.push(sum)
if token == '*' :
product = stack.pop() * stack.pop()
stack.push(product)
else:
stack.push(int(token))
return stack.pop()
A primeira condição cuida de espaços e strings vazias. As duas próximas condições manipulam os operadores. Nós assumimos, agora que qualquer coisa é um operador. É claro, seria melhor chegar por entrada errônea e enviar uma mensagem de erro, mas faremos isto depois.
Vamos testá-lo avaliando a forma pós-fixa de (56 + 47) * 2
>>> print evalPostfix("56 47 + 2 *")
206
XXXthat’s close enough
18.8 Clientes de fornecedores.
Um dos objetivos de um TAD é separar os interesses do fornecedor, quem escreve o código que implementa o TAD, e o cliente, que usa o TAD. O fornecedor tem que se preocupar apenas se a implementação está correta - de acordo com a especificação do TAD - e não como ele será usado.
Inversamente, o cliente assume que a implementação do TAD está correta e não se preocupa com os detalhes. Quando você está usando um tipo nativo do Python, tem o luxo de pensar exclusivamente como um cliente.
É claro, quanto você implementa um TAD, você também tem que escrever código cliente para testá-lo. Neste caso, você faz os dois papéis, o que pode ser confuso. Você deve fazer algum esforçõ para manter a trilha do papel que está fazendo a cada momento.