Guião da 14ª Aula Teórica

Sumário

  1. Desenho de classes: programação baseada em objectos.  Fases:
    1. Declaração das operações suportadas, suas consequências, e forma de utilização: interface da classe.
    2. Definição dos atributos (representação) e das operações ou métodos (mecanismo): implementação.
  2. Exemplo com pilhas.
  3. Definição de sinónimos de tipos com typedef.
  4. Definição do sinónimo Item e vantagens na facilidade de adaptar a classe.
  5. A classe modelo stack.
  6. Noções elementares de eXtreme Programming: desenho de testes antes das classes e desenvolvimento incremental.

Atenção!  Fazer acetatos a partir do código.

Hoje vamos falar um pouco mais sobre desenho de TAD.  

Normalmente os TAD não surgem do nada.  Surgem por serem úteis para resolver um determinado problema.  Vamos então resolver um problema.

Suponhamos que queremos implementar uma calculadora simples.  Esta calculadora deve suportar as operações de adição, subtracção, multiplicação, divisão e potenciação sobre valores de vírgula flutuante (usaremos double).  Para simplificar vamos supor que os parênteses são proibidos.

As expressões a calcular devem ser lidas do canal de entrada cin, ligado ao teclado, e os resultados devem ser escritos no canal de saída cout, ligado ao ecrã.  A calculadora pode calcular várias expressões, pelo que se arbitra que estas são separadas umas das outras pelo símbolo ; (ponto-e-vírgula).  A calculadora termina o cálculo de expressões quando encontra o símbolo . (ponto).

Por exemplo, se a entrada for:

2 + 2 ;
2 * 2.5 .

a saída deve ser

4
5

Para percebermos melhor como resolver o problema, vamos tentar perceber como nós próprios efectuaríamos os cálculos caso tivéssemos acesso a um símbolo de cada vez.  Por símbolo quero dizer ou valores numéricos ou os operadores permitidos.

Seja então a expressão

1 + 4 * 3 / 2 ^ 3 - 2 .

Qualquer um de nós calcula rapidamente o resultado que é...

Exacto: 0,5.

E se só virmos um símbolo de cada vez.  Que fazer?  

Discutir.

Concluir que o melhor é ir guardando os valores e os operadores!  Mas onde?

O.k., vamos passo a passo.  

Primeiro recebemos

1

Que fazer?

Discutir.

Depois recebemos

+ 

Que fazer?

Discutir.  Deixar a dica que talvez seja boa ideia usar um TAD para representar os operadores.

Depois recebemos

4

Pode-se já calcular?

Discutir.

Não!  Porquê?  Porque a seguir pode vir outro operador com maior precedência!

E se agora fosse

+

?

Discutir.

Nesse caso podia-se logo calcular a primeira operação!

O mesmo se a expressão até aqui fosse:

1 * 4 +

!

Mas não é...

Temos de ler mais um símbolo, que é:

*

Calma lá.  Quantos valores já lemos?  E quantos operadores?  E onde os guardamos?

Discutir, mesmo sem concluir.

Depois vem

3

Pouco ajuda...

E depois vem 

/

E agora?

Discutir!

Qual é a regra?  Podem-se calcular todos os operadores em espera que tenham precedência superior ou igual ao que acabámos de ler!

Mas por que ordem?

Discutir.  Concluir que os cálculos prosseguem pela ordem inversa à da leitura!

Ou seja, podemos empilhar as operações!

E os valores?

Discutir.

Uma pilha também serve para os valores!

Exemplificar desde o início ao fim da expressão, desenhando a evolução das pilhas.  Explicar o que acontece no . (ponto).

Então já temos uma ideia da forma de cálculo da nossa calculadora.  Falta definirmos os TAD necessários.

Em primeiro lugar, vai-nos dar muito jeito um TAD para representar os operadores!

Apresentar acetato!  Explicar cuidadosamente a classe.  Explicar o operator()().  Explicar o operador <: um operador é menor que outro se tiver menos precedência.  Explicar membro de classe cuidadosamente!  Dar exemplos de invocação!

Em segundo lugar vai-nos ser útil uma classe para representar a calculadora!  

Apresentar acetato.  Explicar detalhadamente o seu funcionamento.  Deixar claro que não se verificam nenhuns erros do utilizador!  A intenção é simplificar a resolução.  Fica como exercício... Fazer um traçado admitindo a mesma entrada.

Depois de eles se terem convencido da bondade da solução, avançar.

Disse-vos que ia falar do desenho de TAD e na volta apresentei as classes C++ correspondentes já prontas e acabadas...  Batotice...  Bom, não inteiramente.  Faltam as pilhas!

Explicar que ainda não temos os tipos PilhaDeDouble nem PilhaDeOperador, mas que já temos um programa escrito que faz uso da classe!

Esta é uma boa forma de sabermos que operações deve um TAD suportar: começar a resolver o problema assumindo que a classe existe!

Vamos começar pela classe PilhaDeDouble.  A classe PilhaDeOperador será praticamente igual.

Que operações podemos realizar sobre uma pilha?

Discutir.  Concluir:

  1. Criar pilha vazia.
  2. Pôr item na pilha.  Altera a pilha.
  3. Obter o item do topo.  Não altera a pilha!
  4. Tirar o item do topo.  Altera a pilha.
  5. Saber altura da pilha.  Não altera a pilha!
  6. Verificar se está vazia.  Não altera a pilha!

Antes de avançarmos, no entanto, é conveniente, aliás, é fundamental, fazermos aquilo que se chama um teste de unidade.  Um teste de unidade, ou teste de módulo, é um pequeno programa que nos permite testar todas as operações de um TAD, de modo a ficarmos seguros do seu bom funcionamento.

.....

#ifdef TESTE

int main()
{
    PilhaDeDouble pilha;

    assert(pilha.estaVazia());
    assert(pilha.altura() == 0);

    for(int i = 0; i != 10; ++i) {
        assert(pilha.altura() == i);

        pilha.poe(i);

        assert(pilha.itemNoTopo() == i);
        assert(not pilha.estaVazia());
         assert(pilha.altura() == i + 1);
    }

    assert(pilha.itemNoTopo() == 9);
    assert(not pilha.estaVazia());
    assert(pilha.altura() == 10);

    for(int i = 9; i != -1; --i) {
        assert(pilha.itemNoTopo() == i);
        assert(not pilha.estaVazia());
        assert(pilha.altura() == i + 1);

        pilha.tiraItem();

        assert(pilha.altura() == i);
    }

    assert(pilha.estaVazia());
    assert(pilha.altura() == 0);
}

#endif

Explicar bem as directivas de pré-processador, embora sem entrar em pormenores.  Dizer que a função main() só chega a ser compilada se o programa for compilado com um comando da forma:

c++ -DTESTE ...

Agora é só ir definindo a interface da classe C++, incluindo documentação, mas deixando a implementação de lado.

Discutir efeito de cada operação e circunstâncias em que falha.

/** Representa pilhas de double.
    @invariant Dizer que não se conhece por ser questão de implementação. */
class PilhaDeDouble {
  public:
    typedef double Item;

    /** Constrói pilha vazia.
        @pre V.
        @post estaVazia(). */
    PilhaDeDouble();

    /** Devolve o item que está no topo da pilha.
        @pre ¬estaVazia().
        @post itemNoTopo idêntico ao item no topo de *this. */
    Item const& itemNoTopo() const;

    /** Indica se a pilha está vazia.
        @pre V.
        @post estaVazia = *this está vazia. */
    bool estaVazia() const;

    /** Devolve altura da pilha.
        @pre V.
        @post altura = altura de *this. */
    int altura() const;

    /** Põe um novo item na pilha (no topo).
        @pre V.
        @post *this contém um item adicional no topo igual a novo_item. */
    void poe(Item const& novo_item);

    /** Tira o item que está no topo da pilha.
        @pre ¬estaVazia().
        @post *this contém os itens originais menos o do topo. */
    void tiraItem();
 
  private:

    ...

    /** Indica se a CIC se verifica.
        @pre V.
        @post cumpreInvariante = ... . */
    bool cumpreInvariante() const;
};

...

Discutir cuidadosamente o typedef e sua utilidade!  Com Item é fácil alterar o tipo dos itens!

O que fazer para definir a classe PilhaDeOperador?

Discutir.

O que é que falta?  A implementação!  É o menos importante!  Façam-na vocês: fica como exercício.

Conclusões:

  1. Os TAD surgem para auxiliar na resolução de um problema.
  2. A resolução deve ser usada para sugerir as operações necessárias para o novo TAD.
  3. Deve-se começar por escrever o respectivo teste de unidade.
  4. O teste de unidade deve testar todas as operações da classe.
  5. Só então se desenha a interface da classe C++ que implementa o TAD.
  6. Finalmente passa-se à implementação.
  7. A implementação deve ser feita passo a passo, indo-se sempre testando até o teste correr sem problemas.
  8. Para se poder implementar passo-a-passo, convém começar por fazer uma implementação embrionária dos métodos e rotinas, que contém apenas as instruções asserção e, no caso das funções, uma instrução de retorno.

O teste de unidade e a interface da classe podem ser desenvolvidos em paralelo, incrementalmente.  Mas a implementação deve ser deixada para o fim!

Falar de modularização: departamento de marketing + designers definem a interface (o que faz, como se opera, aspecto exterior), departamento de engenharia implementa mecanismo.

Programação baseada em objectos: primeiro pensa-se que classes existem (substantivos no vocabulário do problema).  Depois pensa-se nos algoritmos.  E não o contrário: programação procedimental, em que primeiro se pensa nos algoritmos e só depois nos dados.  Por vezes misturam-se os dois tipos de abordagem.

Se houver tempo discutir um pouco a implementação.

Dizer que as pilhas...  Já existem... #include <stack>... push(), pop(), size(), top(), empty().

Referir que no segundo semestre vamos aprender a escrever o código da pilha uma vez apenas de modo a que seja válido com qualquer tipo: classes genéricas e programação genérica.