Capítulo 18: Pilhas

18.1 Tipos abstratos de dados

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.

18.2 O TAD Pilha

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.

18.3 Implementando pilhas com listas de Python

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.

18.4 Empilhando e desempilhando

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.

18.5 Usando uma pilha para avaliar expressões pós-fixas

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.

18.6 Análise sintática

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.

18.7 Avaliando em pós-fixo.

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.

18.9 Glossário

tipo abstrato de dados (TAD) (abstract data type(ADT)):

Um tipo de dado(geralmente uma coleção de objetos) que é definidopor um conjunto de operações, que podem ser implementadas de várias maneiras.

interface (interface):

É o conjunto de operações que definem um TDA.

implementação (implementation):

Código que satisfaz(preenche?) os requisitos sintáticos e semânticos de uma interface.

cliente (client):

Um programa (ou o programador que o escreveu) que faz utilização de um TDA.

fornecedor (provider):

Código (ou o programador que o escreveu) que implementa um TDA.

revestimento (veneer):

Definição de classe que implementa um TDA com definições de métodos que são chamadas a outros métodos, às vezes com pequenas modificações. A lâmina faz um trabalho insignificante, mas melhora ou padroniza a interface dada ao cliente.

estrutura de dados genérica (generic data structure):

Tipo de estrutura de dados que contem data de um tipo qualquer(tipo genérico).

infixa (infix):

Notação matemática em que os operadores se situam entre os operandos.

pós-fixa (postfix):

Notação matemática em que os operadores se situam após os operandos.

XXX parse (parse):

Ler um conjunto de caracteres(string de caracteres) ou tokens(símbolos atômicos) e analisar sua estrutura gramatical.

XXX token (token):

Conjunto de caracteres que são tratados como uma unidade atômica para fins de análise gramatical, como as palavras na linguagem natural.

delimitador (delimiter):

Um caracter que é utilizado para separar os símbolos atômicos(tokens), como a pontuação na linguagem natural.