Aula 14 Programação Baseada em Objectos Desenho de TAD

  • Published on
    17-Apr-2015

  • View
    102

  • Download
    0

Embed Size (px)

Transcript

<ul><li> Slide 1 </li> <li> Aula 14 Programao Baseada em Objectos Desenho de TAD </li> <li> Slide 2 </li> <li> 2003/2004 Introduo Programao 2 Desenvolver uma calculadora Operaes: + adio - subtraco / diviso * multiplicao ^ potenciao Suporte para double (incluindo negativos) Parnteses proibidos Expresses de cin Resultados em cout Expresses terminam em ; ou. Smbolo. termina execuo da calculadora </li> <li> Slide 3 </li> <li> 2003/2004 Introduo Programao 3 Exemplo Entrada: 2 + 2 ; 2 * 2.5. Sada: 4 5 </li> <li> Slide 4 </li> <li> 2003/2004 Introduo Programao 4 Exerccio Qual o resultado de 2 * 3 + 3 * 5 ^ 2 ; ? E se os smbolos forem lidos um de cada vez? (Smbolos so valores ou operadores, incluindo terminadores) </li> <li> Slide 5 </li> <li> 2003/2004 Introduo Programao 5 Clculo de expresso Smbolo lido: 1 </li> <li> Slide 6 </li> <li> 2003/2004 Introduo Programao 6 Clculo de expresso Que fazer aos smbolos lidos? Ao 1 e ao +? necessrio guard-los algures! Smbolo lido: + </li> <li> Slide 7 </li> <li> 2003/2004 Introduo Programao 7 Clculo de expresso Podemos calcular j 1 + 4? No! Depende do que se segue! Smbolo lido: 4 </li> <li> Slide 8 </li> <li> 2003/2004 Introduo Programao 8 Clculo de expresso Calcular j 1 + 4 teria sido asneira! A no ser que se tivesse lido 1 * 4, ou se o smbolo lido fosse + Nesse caso podamos fazer j o clculo, e escusvamos de memorizar tantos smbolos Smbolo lido: * Memorizar No nosso programa teremos de guardar os smbolos algures! </li> <li> Slide 9 </li> <li> 2003/2004 Introduo Programao 9 Clculo de expresso E a saga continua Smbolo lido: 3 </li> <li> Slide 10 </li> <li> 2003/2004 Introduo Programao 10 Clculo de expresso 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: Ao ler um operador, podemos calcular os operadores em espera enquanto forem de precedncia maior ou igual Smbolo lido: / Por ordem inversa da leitura! Podem-se empilhar os operadores! </li> <li> Slide 11 </li> <li> 2003/2004 Introduo Programao 11 Clculo de expresso Mais uma vez necessrio guardar o valor Se a prxima operao for, por exemplo, +, a diviso calculada entre 12 e 2, que foram os ltimos valores considerados Smbolo lido: 2 Tambm se podem empilhar os valores! </li> <li> Slide 12 </li> <li> 2003/2004 Introduo Programao 12 Regressemos ao incio Vamos recomear o clculo, mas equipando- nos com duas pilhas: Pilha dos operadores Pilha dos valores </li> <li> Slide 13 </li> <li> 2003/2004 Introduo Programao 13 valoresoperadores Clculo de expresso Lido um valor, h que coloc-lo na respectiva pilha Smbolo lido: 1 </li> <li> Slide 14 </li> <li> 2003/2004 Introduo Programao 14 valoresoperadores Clculo de expresso Lido um operador, h que verificar se h algum outro de maior ou igual precedncia na pilha Como no h, h que o colocar na pilha apropriada Smbolo lido: + 1 </li> <li> Slide 15 </li> <li> 2003/2004 Introduo Programao 15 valoresoperadores Clculo de expresso Valores vo sempre para a pilha Smbolo lido: 4 1+ </li> <li> Slide 16 </li> <li> 2003/2004 Introduo Programao 16 valoresoperadores Clculo de expresso Como a multiplicao tem maior precedncia que a soma, que est no topo da pilha, no se pode ainda realizar a soma necessrio, de qualquer forma, colocar a multiplicao no topo da pilha Smbolo lido: * 1+ 4 </li> <li> Slide 17 </li> <li> 2003/2004 Introduo Programao 17 valoresoperadores Clculo de expresso um valor Smbolo lido: 3 1+ 4* </li> <li> Slide 18 </li> <li> 2003/2004 Introduo Programao 18 valoresoperadores Clculo de expresso No topo da pilha h um operador com igual precedncia Antes de guardar a nova operao na pilha, efectua-se a do topo e guarda-se o resultado Smbolo lido: / 1+ 4* 3 = 12 </li> <li> Slide 19 </li> <li> 2003/2004 Introduo Programao 19 valoresoperadores Clculo de expresso Valores vo directos para a pilha, como sempre Smbolo lido: 2 1+ 12/ </li> <li> Slide 20 </li> <li> 2003/2004 Introduo Programao 20 valoresoperadores Clculo de expresso Como a potenciao tem maior precedncia que a diviso, que est no topo da pilha, no se pode ainda realizar a diviso necessrio, de qualquer forma, colocar a potenciao no topo da pilha Smbolo lido: ^ 1+ 12/ 2 </li> <li> Slide 21 </li> <li> 2003/2004 Introduo Programao 21 valoresoperadores Clculo de expresso Pilha com ele! Smbolo lido: 3 1+ 12/ 2^ </li> <li> Slide 22 </li> <li> 2003/2004 Introduo Programao 22 valoresoperadores Clculo de expresso Tm de se realizar todas as operaes com precedncia maior ou igual! Smbolo lido: - 1+ 12/ 2^ 3 = 8 </li> <li> Slide 23 </li> <li> 2003/2004 Introduo Programao 23 valoresoperadores Clculo de expresso Tm de se realizar todas as operaes com precedncia maior ou igual! Smbolo lido: - 1+ 12/ 8 = 1,5 </li> <li> Slide 24 </li> <li> 2003/2004 Introduo Programao 24 valoresoperadores Clculo de expresso Tm de se realizar todas as operaes com precedncia maior ou igual! Depois, guarda-se a operao na pilha Smbolo lido: - 1+ 1,5 = 2,5 </li> <li> Slide 25 </li> <li> 2003/2004 Introduo Programao 25 valoresoperadores Clculo de expresso Mais um Smbolo lido: 2 2,5- </li> <li> Slide 26 </li> <li> 2003/2004 Introduo Programao 26 valoresoperadores Clculo de expresso Ao atingir o smbolo. (ponto), efectuam-se todas as operaes que restam na pilha Smbolo lido:. 2,5- 2 = 0,5 </li> <li> Slide 27 </li> <li> 2003/2004 Introduo Programao 27 valoresoperadores Clculo de expresso Ao atingir o smbolo. (ponto), efectuam-se todas as operaes que restam na pilha O resultado retira-se da pilha dos valores: Smbolo lido: 0,5 </li> <li> Slide 28 </li> <li> 2003/2004 Introduo Programao 28 E agora? necessrio escrever o programa Mas j se sabe que ferramentas esto em falta: Um TAD para representar operadores Um TAD para representar uma calculadora E </li> <li> Slide 29 </li> <li> 2003/2004 Introduo Programao 29 TAD Operador Representa operadores (binrios) que podem ser +, -, *, / ou ^ Construtor deve receber smbolo indicando operao a realizar Deve possuir operao para calcular resultado da sua aplicao a dois operandos double </li> <li> Slide 30 </li> <li> 2003/2004 Introduo Programao 30 TAD Operador /** Representa um operador aritmtico, com o qual se podem realizar operaes. @invariant ?. */ class Operador { public: }; </li> <li> Slide 31 </li> <li> 2003/2004 Introduo Programao 31 Construtor Operador::Operador() /** */ class Operador { public: /** Constri um novo operador correspondente ao smbolo dado. @pre smbolo pertence a { '+', '-', '*', '/', '^' }. @post Operador o operador representado por smbolo. */ explicit Operador(char const smbolo); }; Cdigo possvel: Operador multiplicao(*); A utilizao de explicit impede a converso implcita de char em Operador. </li> <li> Slide 32 </li> <li> 2003/2004 Introduo Programao 32 Operao Operador::operator()() /** */ class Operador { public: /** 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 parnteses usado na invocao de rotinas. um operador n-rio, que pode ser sobrecarregado! Cdigo possvel: Operador multiplicao(*); cout = a no implica que a == b, mas sim que a e b tm a mesma precedncia. @pre V. @post operador== = ( *this representa o mesmo operador que outro_operador ). */ bool operator==(Operador const&amp; outro_operador) const; }; Cdigo possvel: Operador multiplicao(*); Operador adio(+); if(adio == multiplicao) </li> <li> Slide 35 </li> <li> 2003/2004 Introduo Programao 35 Operao Operador::smboloVlido() /** */ class Operador { public: /** Verifica se um smbolo representao de algum dos operadores suportados. @pre V. @post smbolo pertence a { '+', '-', '*', '/', '^' }. */ static bool smboloVlido(char const smbolo); }; Cdigo possvel: char smbolo; cin &gt;&gt; smbolo; if(not Operador::smboloVlido(smbolo)) cout </li> <li> 2003/2004 Introduo Programao 51 Mtodo Calculadora::executa() if(Operador::simboloVlido(caractere)) { efectuaOperaesDePrecednciaMaiorOuIgualA(Operador(caractere)); pilha_de_operadores.pe(Operador(caractere)); } else if(caractere == ';' or caractere == '.') { efectuaTodasAsOperaes(); cout valor; pilha_de_valores.pe(valor); } </li> <li> Slide 52 </li> <li> 2003/2004 Introduo Programao 52 Mtodo Calculadora:: efectuaOperaoNoTopo() void Calculadora::efectuaOperaoNoTopo() { assert(1 = operador) efectuaOperaoNoTopo(); } </li> <li> Slide 54 </li> <li> 2003/2004 Introduo Programao 54 Mtodo Calculadora:: efectuaTodasAsOperaes() void Calculadora::efectuaTodasAsOperaes() { while(not pilha_de_operadores.estVazia()) efectuaOperaoNoTopo(); assert(pilha_de_operadores.estVazia()); } </li> <li> Slide 55 </li> <li> 2003/2004 Introduo Programao 55 Mtodo Calculadora:: cumpreInvariante() bool Calculadora::cumpreInvariante() const { return pilha_de_valores.estVazia() and pilha_de_operadores.estVazia(); } </li> <li> Slide 56 </li> <li> 2003/2004 Introduo Programao 56 E as pilhas? Programa escrito usa-as Necessrio desenvolv-las Desenho de TAD ser demonstrado com as pilhas </li> <li> Slide 57 </li> <li> 2003/2004 Introduo Programao 57 Desenho de TAD Recomendvel comear por escrever restante cdigo assumindo que existem Recomendvel tambm escrever programa de teste Ambos clarificam operaes e comportamentos desejveis, bem como a interface desejvel </li> <li> Slide 58 </li> <li> 2003/2004 Introduo Programao 58 Operaes das pilhas Construir pilha vazia Verificar se est vazia Obter o item do topo Saber altura da pilha Pr item na pilha Tirar o item do topo construtores predicados (inspectores) inspectores modificadores Comearemos por PilhaDeDouble </li> <li> Slide 59 </li> <li> 2003/2004 Introduo Programao 59 TAD PilhaDeDouble : Teste de unidade int main() { PilhaDeDouble pilha; assert(pilha.estVazia()); 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.estVazia()); assert(pilha.altura() == i + 1); } (continua) </li> <li> Slide 60 </li> <li> 2003/2004 Introduo Programao 60 TAD PilhaDeDouble : Teste de unidade (continuao) assert(pilha.itemNoTopo() == 9); assert(not pilha.estVazia()); assert(pilha.altura() == 10); for(int i = 9; i != -1; --i) { assert(pilha.itemNoTopo() == i); assert(not pilha.estVazia()); assert(pilha.altura() == i + 1); pilha.tiraItem(); assert(pilha.altura() == i); } assert(pilha.estVazia()); assert(pilha.altura() == 0); } </li> <li> Slide 61 </li> <li> 2003/2004 Introduo Programao 61 TAD PilhaDeDouble /** Representa pilhas de double. @invariant [o invariante um problema de implementao]. */ 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 definio de Item de double para Operador. </li> <li> Slide 62 </li> <li> 2003/2004 Introduo Programao 62 TAD PilhaDeDouble : Construtores /** */ class PilhaDeDouble { public: /** Constri pilha vazia. @pre V. @post estVazia (). */ PilhaDeDouble(); }; </li> <li> Slide 63 </li> <li> 2003/2004 Introduo Programao 63 TAD PilhaDeDouble : Predicados /** */ class PilhaDeDouble { public: /** Indica se a pilha est vazia. @pre V. @post estVazia = *this est vazia. */ bool estVazia() const; }; </li> <li> Slide 64 </li> <li> 2003/2004 Introduo Programao 64 TAD PilhaDeDouble : Inspectores /** */ class PilhaDeDouble { public: /** Devolve o item que est no topo da pilha. @pre estVazia (). @post itemNoTopo idntico ao item no topo de *this. */ Item const&amp; itemNoTopo() const; /** Devolve altura da pilha. @pre V. @post altura = altura de *this (nmero de itens). */ int altura() const; }; </li> <li> Slide 65 </li> <li> 2003/2004 Introduo Programao 65 TAD PilhaDeDouble : Modificadores /** */ class PilhaDeDouble { public: /** Pe um novo item na pilha (no topo). @pre V. @post *this contm um item adicional no topo igual a novo_item. */ void pe(Item const&amp; novo_item); /** Tira o item que est no topo da pilha. @pre estVazia (). @post *this contm os itens originais menos o do topo. */ void tiraItem(); private: }; </li> <li> Slide 66 </li> <li> 2003/2004 Introduo Programao 66 TAD PilhaDeDouble : Implementao Fica como exerccio </li> <li> Slide 67 </li> <li> 2003/2004 Introduo Programao 67 Estrutura global do programa #include #include // define, &gt;= e != custa de &lt; e de ==. #include #include // para isdigit(). #include // para pow(). #include // outras incluses necessrias para as pilhas. using namespace std; using namespace std::rel_ops; // para definies de </li></ul>