Aula 14
Programação Baseada em Objectos
Desenho de TAD
Desenvolver uma calculadora

Operações:
+ – adição
- – subtracção
/ – divisão
* – multiplicação
^ – potenciação






2
Suporte para double (incluindo negativos)
Parênteses proibidos
Expressões de cin
Resultados em cout
Expressões terminam em ; ou .
Símbolo . termina execução da calculadora
Introdução à Programação
2003/2004
Exemplo

Entrada:
2 + 2 ;
2 * 2.5 .

Saída:
4
5
3
Introdução à Programação
2003/2004
Exercício

Qual o resultado de 2 * 3 + 3 * 5 ^ 2 ; ?

E se os símbolos forem lidos um de cada vez?
(Símbolos são valores ou operadores,
incluindo terminadores)
4
Introdução à Programação
2003/2004
Cálculo de expressão
Símbolo
lido:
5
1
Introdução à Programação
2003/2004
Cálculo de expressão
Símbolo
lido:
6
+

Que fazer aos símbolos
lidos? Ao 1 e ao +?

É necessário guardá-los
algures!
Introdução à Programação
2003/2004
Cálculo de expressão
Símbolo
lido:
7
4

Podemos calcular já
1 + 4?

Não! Depende do que
se segue!
Introdução à Programação
2003/2004
Cálculo de expressão
Símbolo
lido:
*
Memorizar… No
nosso programa
teremos de guardar
os símbolos algures!
8

Calcular já 1 + 4 teria
sido asneira!

A não ser que se tivesse
lido 1 * 4, ou se o
símbolo lido fosse +

Nesse caso podíamos
fazer já o cálculo, e
escusávamos de
memorizar tantos
símbolos
Introdução à Programação
2003/2004
Cálculo de expressão
Símbolo
lido:
9
3

Introdução à Programação
E a saga continua
2003/2004
Cálculo de expressão
Símbolo
lido:

Podemos calcular o produto
anterior, ou seja, 4 * 3!

O resultado do produto tem de
ser guardado

O produto é o dos dois últimos
valores lidos

Regra:
/
Por ordem inversa à
da leitura!
Podem-se empilhar
os operadores!
10
Introdução à Programação
Ao ler um operador, podemos
calcular os operadores em
espera enquanto forem de
precedência maior ou igual
2003/2004
Cálculo de expressão
Símbolo
lido:
2

Mais uma vez é
necessário guardar o
valor

Se a próxima operação
for, por exemplo, +, a
divisão é calculada entre
12 e 2, que foram os
últimos valores
considerados
Também se podem
empilhar os valores!
11
Introdução à Programação
2003/2004
Regressemos ao início

12
Vamos recomeçar o cálculo, mas equipandonos com duas pilhas:

Pilha dos operadores

Pilha dos valores
Introdução à Programação
2003/2004
Cálculo de expressão
Símbolo
lido:
operadores
13

1
Lido um valor, há que
colocá-lo na respectiva
pilha
valores
Introdução à Programação
2003/2004
Cálculo de expressão
Símbolo
lido:

+

Lido um operador, há
que verificar se há algum
outro de maior ou igual
precedência na pilha
Como não há, há que o
colocar na pilha
apropriada
1
operadores
14
valores
Introdução à Programação
2003/2004
Cálculo de expressão
Símbolo
lido:

4
+
1
operadores
valores
15
Introdução à Programação
Valores vão sempre para
a pilha
2003/2004
Cálculo de expressão
Símbolo
lido:

*

4
+
1
operadores
valores
16
Introdução à Programação
Como a multiplicação
tem maior precedência
que a soma, que está no
topo da pilha, não se
pode ainda realizar a
soma
É necessário, de
qualquer forma, colocar
a multiplicação no topo
da pilha
2003/2004
Cálculo de expressão
Símbolo
lido:

3
*
4
+
1
operadores
valores
17
Introdução à Programação
É um valor…
2003/2004
Cálculo de expressão
Símbolo
lido:

/

3
*
4
+
1
operadores
valores
18
No topo da pilha há um
operador com igual
precedência
Antes de guardar a nova
operação na pilha,
efectua-se a do topo e
guarda-se o resultado
=
Introdução à Programação
12
2003/2004
Cálculo de expressão
Símbolo
lido:

2
/
12
+
1
operadores
valores
19
Introdução à Programação
Valores vão directos
para a pilha, como
sempre
2003/2004
Cálculo de expressão
Símbolo
lido:

^

2
/
12
+
1
operadores
valores
20
Introdução à Programação
Como a potenciação tem
maior precedência que a
divisão, que está no topo
da pilha, não se pode
ainda realizar a divisão
É necessário, de
qualquer forma, colocar
a potenciação no topo da
pilha
2003/2004
Cálculo de expressão
Símbolo
lido:

3
^
2
/
12
+
1
operadores
valores
21
Introdução à Programação
Pilha com ele!
2003/2004
Cálculo de expressão
Símbolo
lido:

-
Têm de se realizar todas
as operações com
precedência maior ou
igual!
3
^
2
/
12
+
1
operadores
valores
22
=
Introdução à Programação
8
2003/2004
Cálculo de expressão
Símbolo
lido:

-
Têm de se realizar todas
as operações com
precedência maior ou
igual!
8
/
12
+
1
operadores
valores
23
=
Introdução à Programação
1,5
2003/2004
Cálculo de expressão
Símbolo
lido:

-

=
1,5
+
1
operadores
valores
24
Têm de se realizar todas
as operações com
precedência maior ou
igual!
Depois, guarda-se a
operação na pilha
Introdução à Programação
2,5
2003/2004
Cálculo de expressão
Símbolo
lido:

2
-
2,5
operadores
valores
25
Introdução à Programação
Mais um…
2003/2004
Cálculo de expressão
Símbolo
lido:

.
=
2
-
2,5
operadores
valores
26
Ao atingir o símbolo .
(ponto), efectuam-se
todas as operações que
restam na pilha
Introdução à Programação
0,5
2003/2004
Cálculo de expressão

Símbolo
lido:

Ao atingir o símbolo .
(ponto), efectuam-se
todas as operações que
restam na pilha
O resultado retira-se da
pilha dos valores:
0,5
operadores
27
valores
Introdução à Programação
2003/2004
E agora?

É necessário escrever o programa…

Mas já se sabe que ferramentas estão em
falta:



28
Um TAD para representar operadores
Um TAD para representar uma calculadora
E…
Introdução à Programação
2003/2004
TAD Operador

Representa operadores (binários) que podem
ser +, -, *, / ou ^

Construtor deve receber símbolo indicando
operação a realizar

Deve possuir operação para calcular resultado
da sua aplicação a dois operandos double
29
Introdução à Programação
2003/2004
TAD Operador
/** Representa um operador aritmético, com o qual se podem realizar operações.
@invariant ?. */
class Operador {
public:
…
};
30
Introdução à Programação
2003/2004
Construtor
Operador::Operador()
A utilização de explicit
impede a conversão implícita
de char em Operador.
/** … */
class Operador {
public:
/** Constrói um novo operador correspondente ao símbolo dado.
@pre símbolo pertence a {'+', '-', '*', '/', '^'}.
@post Operador é o operador representado por símbolo. */
explicit Operador(char const símbolo);
…
};
Código possível:
Operador multiplicação(‘*’);
31
Introdução à Programação
2003/2004
Operação
Operador::operator()()
/** … */
class Operador {
public:
Chiça!
…
/** Devolve o resultado do operador quando aplicado aos operandos dados.
@pre *this ≠ Operador(‘/’)  operando_direito ≠ 0.
@post operator() = operando_esquerdo *this operando_direito. */
double operator()(double const operando_esquerdo,
double const operando_direito) const;
…
};
O operador parênteses é usado na invocação de
rotinas. É um operador n-ário, que pode ser
sobrecarregado!
Código possível:
32
Operador multiplicação(‘*’);
cout << multiplicação(2.0, 3.0) << endl;
Introdução à Programação
2003/2004
Operação
Operador::operator<()
/** … */
class Operador {
public:
…
/** Verifica se o operador tem menor precedência que o operador dado.
@pre V.
@post operador< = (precedência de *this é menor que a de
outro_operador). */
bool operator<(Operador const& outro_operador) const;
…
};
Código possível:
Operador multiplicação(‘*’);
Operador adição(‘+’);
if(adição < multiplicação)
…
33
Introdução à Programação
2003/2004
Operação
Operador::operator==()
/** … */
class Operador {
public:
…
/** Verifica se o operador é igual ao operador dado. Note-se que a >= b e b >= a
não implica que a == b, mas sim que a e b têm a mesma precedência.
@pre V.
@post operador== = (*this representa o mesmo operador que
outro_operador). */
bool operator==(Operador const& outro_operador) const;
…
Código possível:
};
Operador multiplicação(‘*’);
Operador adição(‘+’);
if(adição == multiplicação)
…
34
Introdução à Programação
2003/2004
Operação
Operador::símboloÉVálido()
Um membro qualificado com static diz-se de
/** … */
class Operador {
public:
…
classe. Se for uma operação, não tem instância
implícita. As únicas diferenças para uma rotina
não-membro são os privilégios de acesso a
membros privados e o nome qualificado com o
nome da classe.
/** Verifica se um símbolo é representação de algum dos operadores suportados.
@pre V.
@post símbolo pertence a {'+', '-', '*', '/', '^'}. */
static bool símboloÉVálido(char const símbolo);
…
Código possível:
};
35
char símbolo;
cin >> símbolo;
if(not Operador::símboloÉVálido(símbolo))
cout << “…” << endl;
else {
Operador operador(símbolo);
…
} Introdução à Programação
2003/2004
TAD Operador: Implementação
/** Representa um operador aritmético, com o qual se podem realizar operações.
@invariant símbolo pertence a {'+', '-', '*', '/', '^'}. */
class Operador {
…
private:
/** Indica se o invariante da classe é cumprido.
@pre V.
@post símbolo pertence a {'+', '-', '*', '/', '^'}. */
bool cumpreInvariante() const;
char símbolo;
};
36
Introdução à Programação
2003/2004
Construtor
Operador::Operador()
inline Operador::Operador(char const símbolo)
: símbolo(símbolo)
{
assert(símboloÉVálido(símbolo));
assert(cumpreInvariante());
}
37
Introdução à Programação
2003/2004
Método
Operador::operator()()
double Operador::operator()(double const operando_esquerdo,
double const operando_direito) const
{
assert(cumpreInvariante());
assert(símbolo != '/' or operando_direito != 0);
switch(símbolo) {
case '+':
return operando_esquerdo + operando_direito;
case '-':
return operando_esquerdo - operando_direito;
case '*':
return operando_esquerdo * operando_direito;
case '/':
return operando_esquerdo / operando_direito;
case '^':
return pow(operando_esquerdo, operando_direito);
}
}
38
Introdução à Programação
2003/2004
Método
Operador::operator<()
inline bool Operador::operator<(Operador const& outro_operador) const
{
assert(cumpreInvariante());
switch(símbolo) {
case '+':
case '-':
return outro_operador.símbolo
outro_operador.símbolo ==
outro_operador.símbolo ==
case '*':
case '/':
return outro_operador.símbolo
case '^':
return false;
}
== '*' or
'/' or
'^';
== '^';
}
39
Introdução à Programação
2003/2004
Método
Operador::operator==()
inline
bool Operador::operator==(Operador const& outro_operador) const
{
assert(cumpreInvariante());
return símbolo == outro_operador.símbolo;
}
40
Introdução à Programação
2003/2004
Método
Operador::símboloÉVálido()
inline bool Operador::símboloÉVálido(char const símbolo)
{
return símbolo == '+' or símbolo == '-' or
símbolo == '*' or símbolo == '/' or
símbolo == '^';
}
41
Introdução à Programação
2003/2004
Método
Operador::cumpreInvariante()
inline bool Operador::cumpreInvariante() const
{
return símboloÉVálido(símbolo);
}
42
Introdução à Programação
2003/2004
TAD Calculadora

Representa uma calculadora

Para ser mais curto e legível, o código não
verifica nenhum possível erro do utilizador!
43
Introdução à Programação
2003/2004
TAD Calculadora
/** Representa uma calculadora que opera sobre expressões lidas do canal cin,
escrevendo o resultado em cout. As expressões podem envolver os operadores
binários +, -, *, / e ^ (potenciação). Não podem incluir parênteses. As expressões
são separadas por ; (ponto-e-vírgula) e terminadas por . (ponto).
@invariant ?. */
class Calculadora {
public:
…
};
44
Introdução à Programação
2003/2004
Operação
Calculadora::executa()
/** … */
class Calculadora {
public:
/** Executa a calculadora sobre expressões presentes no canal cin.
@pre As expressões no canal cin têm de estar sintacticamente correctas, estar
separadas por ; (ponto-e-vírgula) e a sua sequência deve ser terminada
por . (ponto).
@post O canal cout contém os resultados de todas as expressões,
um em cada linha. */
void executa();
…
};
45
Introdução à Programação
2003/2004
TAD Calculadora:
Implementação
/** Representa uma calculadora que opera sobre expressões lidas do canal cin,
escrevendo o resultado em cout. As expressões podem envolver os operadores
binários +, -, *, / e ^ (potenciação). Não podem incluir parênteses. As expressões
são separadas por ; (ponto-e-vírgula) e terminadas por . (ponto).
@invariant pilha_de_valores.empty()  pilha_de_operadores.empty(). */
class Calculadora {
…
private:
…
/** Indica se o invariante da classe é cumprido.
@pre V.
@post pilha_de_valores.estáVazia() 
pilha_de_operadores. estáVazia(). */
bool cumpreInvariante() const;
};
46
PilhaDeDouble pilha_de_valores;
PilhaDeOperador pilha_de_operadores;
Introdução à Programação
2003/2004
Operação Calculadora::
efectuaOperaçãoNoTopo()
/** … */
class Calculadora {
…
private:
/** Efectua operação correspondente ao operador que se encontra no topo da pilha
de operadores usando como operandos os dois valores no topo da pilha de
valores. O valor que se encontra no topo da pilha de valores é o operando
direito, sendo o valor imediatamente abaixo o operando esquerdo.
@pre 1 ≤ pilha_de_operadores.altura() 
2 ≤ pilha_de_valores.altura().
@post Pilha de valores deixou de conter os dois valores do topo, tendo sido
colocado no lugar deles o resultado do operador do topo da pilha de
operadores (que entretanto foi retirado) quando aplicado aos dois valores
retirados (o primeiro valor retirado da pilha de valores é o operando
direito). */
void efectuaOperaçãoNoTopo();
…
};
47
Introdução à Programação
2003/2004
Operação Calculadora::
efectuaOperacoesDePrecedenciaMaiorOuIgualA()
/** … */
class Calculadora {
…
private:
…
/** Efectua os cálculos de todos os operadores de precedência superior
ou igual ao operador passado como argumento.
@pre n = pilha_de_operadores.altura()  k = número de operadores na
pilha de operadores com precedência superior ou igual a operador 
m = pilha_de_valores.altura()  k + 1 ≤ m.
@post pilha_de_operadores.altura() = n – k 
pilha_de_valores.altura() = m – k – 1. */
void efectuaOperaçõesDePrecedênciaMaiorOuIgualA(
Operador const& operador);
…
};
48
Introdução à Programação
2003/2004
Operação Calculadora::
efectuaTodasAsOperações()
/** … */
class Calculadora {
…
private:
…
/** Efectua os cálculos de todos os operadores que estão na pilha.
@pre n = pilha_de_operadores.altura() 
m = pilha_de_valores.altura() 
n + 1 <= m.
@post pilha_de_operadores.estáVazia() 
pilha_de_valores.altura() = m – n – 1. */
void efectuaTodasAsOperações();
…
};
49
Introdução à Programação
2003/2004
Método
Calculadora::executa()
void Calculadora::executa()
{
assert(cumpreInvariante());
char caractere;
do {
cin >> caractere;
if(not cin.fail())
if(Operador::simboloÉVálido(caractere)) {
// Processamento de operador.
} else if(caractere == ';' or caractere == '.') {
// Processamento de terminador.
} else if(isdigit(caractere)) {
// Processamento de valor.
}
} while(not cin.fail() and caractere != '.');
assert(cumpreInvariante());
}
50
Introdução à Programação
2003/2004
Método
Calculadora::executa()
…
if(Operador::simboloÉVálido(caractere)) {
efectuaOperaçõesDePrecedênciaMaiorOuIgualA(Operador(caractere));
pilha_de_operadores.põe(Operador(caractere));
} else if(caractere == ';' or caractere == '.') {
efectuaTodasAsOperações();
cout << pilha_de_valores.itemNoTopo() << endl;
pilha_de_valores.tiraItem();
} else if(isdigit(caractere)) {
cin.putback(caractere);
double valor;
cin >> valor;
pilha_de_valores.põe(valor);
}
…
51
Introdução à Programação
2003/2004
Método Calculadora::
efectuaOperaçãoNoTopo()
void Calculadora::efectuaOperaçãoNoTopo()
{
assert(1 <= pilha_de_operadores.altura());
assert(2 <= pilha_de_valores.altura());
double operando_direito = pilha_de_valores.itemNoTopo();
pilha_de_valores.tiraItem();
double operando_esquerdo = pilha_de_valores.itemNoTopo();
pilha_de_valores.tiraItem();
Operador operador = pilha_de_operadores.itemNoTopo();
pilha_de_operadores.tiraItem();
pilha_de_valores.põe(operador(operando_esquerdo,
operando_direito));
}
52
Introdução à Programação
2003/2004
Método Calculadora::
efectuaOperacoesDeMaiorPrecedenciaQue()
void Calculadora::efectuaOperaçõesDePrecedênciaMaiorOuIgualA(
Operador const& operador)
{
while(not pilha_de_operadores.estáVazia() and
pilha_de_operadores.itemNoTopo() >= operador)
efectuaOperaçãoNoTopo();
}
53
Introdução à Programação
2003/2004
Método Calculadora::
efectuaTodasAsOperações()
void Calculadora::efectuaTodasAsOperações()
{
while(not pilha_de_operadores.estáVazia())
efectuaOperaçãoNoTopo();
assert(pilha_de_operadores.estáVazia());
}
54
Introdução à Programação
2003/2004
Método Calculadora::
cumpreInvariante()
bool Calculadora::cumpreInvariante() const
{
return pilha_de_valores.estáVazia() and
pilha_de_operadores.estáVazia();
}
55
Introdução à Programação
2003/2004
E as pilhas?

Programa escrito usa-as

Necessário desenvolvê-las

Desenho de TAD será demonstrado com as
pilhas
56
Introdução à Programação
2003/2004
Desenho de TAD

Recomendável começar por escrever restante
código assumindo que existem

Recomendável também escrever programa de
teste

Ambos clarificam operações e
comportamentos desejáveis, bem como a
interface desejável
57
Introdução à Programação
2003/2004
Operações das pilhas
Começaremos por
PilhaDeDouble






58
Construir pilha vazia
Verificar se está vazia
Obter o item do topo
Saber altura da pilha
Pôr item na pilha
Tirar o item do topo
Introdução à Programação
construtores
predicados (inspectores)
inspectores
modificadores
2003/2004
TAD PilhaDeDouble:
Teste de unidade
int main()
{
PilhaDeDouble pilha;
assert(pilha.estáVazia());
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.estáVazia());
assert(pilha.altura() == i + 1);
}
(continua)
59
Introdução à Programação
2003/2004
TAD PilhaDeDouble:
Teste de unidade
(continuação)
assert(pilha.itemNoTopo() == 9);
assert(not pilha.estáVazia());
assert(pilha.altura() == 10);
for(int i = 9; i != -1; --i) {
assert(pilha.itemNoTopo() == i);
assert(not pilha.estáVazia());
assert(pilha.altura() == i + 1);
pilha.tiraItem();
assert(pilha.altura() == i);
}
assert(pilha.estáVazia());
assert(pilha.altura() == 0);
}
60
Introdução à Programação
2003/2004
TAD PilhaDeDouble
/** Representa pilhas de double.
@invariant [o invariante é um problema de implementação]. */
class PilhaDeDouble {
public:
typedef double Item;
…
};
Permite alterar o tipo dos itens com muita
facilidade.
Definir PilhaDeOperador torna-se trivial:
a) Copiar classe PilhaDeDouble completa.
b) Substituir PilhaDeDouble por
PilhaDeOperador.
c) Alterar definição de Item de double para
Operador.
61
Introdução à Programação
2003/2004
TAD PilhaDeDouble:
Construtores
/** … */
class PilhaDeDouble {
public:
…
/** Constrói pilha vazia.
@pre V.
@post estáVazia(). */
PilhaDeDouble();
…
};
62
Introdução à Programação
2003/2004
TAD PilhaDeDouble:
Predicados
/** … */
class PilhaDeDouble {
public:
…
/** Indica se a pilha está vazia.
@pre V.
@post estáVazia = *this está vazia. */
bool estáVazia() const;
…
};
63
Introdução à Programação
2003/2004
TAD PilhaDeDouble:
Inspectores
/** … */
class PilhaDeDouble {
public:
…
/** Devolve o item que está no topo da pilha.
@pre ¬estáVazia().
@post itemNoTopo idêntico ao item no topo de *this. */
Item const& itemNoTopo() const;
/** Devolve altura da pilha.
@pre V.
@post altura = altura de *this (número de itens). */
int altura() const;
…
};
64
Introdução à Programação
2003/2004
TAD PilhaDeDouble:
Modificadores
/** … */
class PilhaDeDouble {
public:
…
/** 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 põe(Item const& novo_item);
/** Tira o item que está no topo da pilha.
@pre ¬estáVazia().
@post *this contém os itens originais menos o do topo. */
void tiraItem();
private:
…
};
65
Introdução à Programação
2003/2004
TAD PilhaDeDouble:
Implementação

66
Fica como exercício
Introdução à Programação
2003/2004
Estrutura global do programa
#include
#include
#include
#include
#include
#include
<iostream>
<utility>
<cassert>
<cctype>
<cmath>
…
// define <=, >, >= e != à custa de < e de ==.
// para isdigit().
// para pow().
// outras inclusões necessárias para as pilhas.
using namespace std;
using namespace std::rel_ops; // para definições de <= etc. terem efeito.
class Operador {…} // e respectivos métodos.
class PilhaDeDouble {…} // e respectivos métodos.
class PilhaDeOperador {…} // e respectivos métodos.
class Calculadora {…} // e respectivos métodos.
(continua)
67
Introdução à Programação
2003/2004
Estrutura global do programa
(continuação)
#ifdef TESTE
int main()
{
// Testes das várias classes!
}
Para compilar os testes
usa-se um comando de
compilação semelhante a:
c++ -DTESTE …
#else // TESTE
int main()
{
Calculadora calculadora;
calculadora.executa();
}
#endif // TESTE
68
Introdução à Programação
2003/2004
Programação procedimental

Primeiro pensa-se nos algoritmos

Depois pensa-se nos dados
69
Introdução à Programação
2003/2004
Programação baseada em
objectos

Primeiro pensa-se nos dados (TAD)

Depois pensa-se nos algoritmos
Frequentemente são os substantivos
mais importantes que surgem na
descrição do problema.
70
Introdução à Programação
2003/2004
Desenho de TAD

TAD são módulos

Designers e departamento marketing definem
interface

Engenharia desenvolve o mecanismo
71
Introdução à Programação
2003/2004
Desenho de TAD






Surgem para auxiliar resolução de problema
Resolução usada para sugerir operações necessárias
no TAD
Começa-se pelo teste de unidade
Teste de unidade testa todas as operações do TAD
Depois desenha-se a interface do TAD
Finalmente implementa-se:


72
Passo a passo, testando a cada passo
Se necessário fazer implementação embrionária de
métodos e rotinas (apenas instruções asserção e nas
funções uma instrução de retorno).
Introdução à Programação
2003/2004
Alerta!

Há pilhas na biblioteca do C++:
#include <stack>
#include <iostream>
using namespace std;
int main()
{
stack<int> pilha;
pilha.push(1);
pilha.push(2);
while(not pilha.empty()) {
cout << pilha.top() << endl;
pilha.pop();
}
}
73
Introdução à Programação
2003/2004
Aula 14: Sumário


Desenho de TAD: programação baseada em objectos
Fases:







Exemplo com pilhas.
Definição de sinónimos de tipos com typedef
Classe genérica stack
Noções elementares de eXtreme Programming:


74
Escrita de testes
Declaração das operações suportadas, suas
consequências, e forma de utilização: interface
Definição dos atributos (representação) e dos métodos
(mecanismo): implementação.
Testes primeiro
Desenvolvimento incremental
Introdução à Programação
2003/2004