Gabarito_lista5 ESTRUTURA DE DADOS

Prévia do material em texto

Gabarito - Lista 5 
Pilha 
 
 
1. Faça um programa em C++ para ler um número inteiro maior que zero, converter este número de 
decimal para binário, usando pilha e apresentar na tela, o resultado da conversão. 
 
Gabarito : 
 
#include <iostream> 
using namespace std; 
 
#define TAM 10 
 
//tipo 
 
struct pilha { 
 int topo, 
 v[TAM]; 
 } ; 
 
 
/* codigo das funcoes */ 
 
void empilha (pilha &p, int valor) 
{ 
 
 if (p.topo == TAM-1) 
 { 
 cout << "ERRO : Estouro de pilha.\nFim do programa. " << endl; 
 system("pause"); 
 exit(0); //termina o programa - atitude radical 
 } 
 ++p.topo; 
 p.v[p.topo] = valor; 
 
} 
 
int desempilha (pilha &p) 
{ 
 /* nao trata pilha vazia, pois isto sera tratado na main */ 
 int valor = p.v[p.topo]; 
 p.topo--; 
 return (valor); /* vai decrementar depois o topo */ 
} 
 
/* programa principal */ 
 
int main() 
{ 
 
 int num; 
 pilha pi; 
 
 cout << "PROGRAMA QUE CONVERTE DE DECIMAL PARA BINARIO \n"; 
 
 
 
 do { 
 cout << "\n Digite valor maior que zero : "; 
 cin >> num; 
 } while (num <= 0); /* pára o loop quando num for > que zero */ 
 
 pi.topo = -1; /* inicializa a pilha pi */ 
 while (num > 0) 
 { 
 empilha (pi, num%2); /* empilha o resto*/ 
 num = num/2; 
 } 
 cout << "\n Resultado da conversao : "; 
 while (pi.topo != -1 ) /* enquanto pilha não vazia */ 
 cout << " " << desempilha(pi); /* imprime o resultado do desempilha */ 
 
 cout << endl << endl; 
 system("pause"); 
} 
 
 
2. Construa um programa em C++, que use a estrutura pilha e verifique se o número de abre parênteses 
é igual ao número de fecha parênteses. 
 
Gabarito : 
 
#include <iostream> 
 
using namespace std; 
 
#define TAM 10 
 
//tipo 
 
struct pilha { 
 int topo; 
 char v[TAM]; 
 } ; 
 
 
//PROTÓTIPO 
void empilha (pilha &, char ); 
 
 
//PROGRAMA PRINCIPAL 
 
int main() 
{ 
 
 char exp[30]; 
 pilha pilhaAbre, pilhaFecha; 
 int i; 
 
 cout << "Expressao balanceada ? Vamos ver ! \n"; 
 
 
 cout << "\nForneca a expressao : "; 
 cin.getline(exp,30); 
 
 
 pilhaAbre.topo = -1; //inicializa a pilha de abre parênteses 
 pilhaFecha.topo = -1; //inicializa a pilha de fecha parênteses 
 i = 0; //inicializa o índice do vetor 
 while (exp[i] != '\0') 
 { 
 if (exp[i] == '(') 
 empilha (pilhaAbre, exp[i]); 
 else 
 if (exp[i] == ')') 
 empilha (pilhaFecha, exp[i]); 
 
 i++; //incrementa o índice do vetor 
 } 
 
 if (pilhaAbre.topo == pilhaFecha.topo) 
 cout << "O numero de abre parenteses eh igual ao numero de fecha parenteses. " << endl; 
 else 
 cout << "O numero de abre parenteses NAO eh igual ao numero de fecha parenteses. " << endl; 
 
 
 cout << endl << endl; 
 system("pause"); 
} 
 
//DEFINIÇÃO DA FUNÇÃO DE EMPILHAMENTO 
 
void empilha (pilha &p, char valor) 
{ 
 
 if (p.topo == TAM-1) 
 { 
 cout << "ERRO : Estouro de pilha.\nFim do programa. " << endl; 
 system("pause"); 
 exit(0); //termina o programa - atitude radical 
 } 
 ++p.topo; 
 p.v[p.topo] = valor; 
 
} 
 
 
3. Uma palavra é um palíndromo se a seqúência de letras que a forma é a mesma, quer seja lida da 
esquerda para a direita ou da direita para a esquerda (exemplo: raiar, ovo, ana, mussum). 
Escreva um programa em C++ que reconheça se uma dada palavra é uma palíndromo. 
 
Gabarito : 
 
 
#include <iostream> 
#include <string> 
 
using namespace std; 
 
#define MAX 100 
 
struct PILHA { 
 int topo; 
 char vetp[MAX]; 
}; 
 
//Só trabalhei com global para comentar mais uma vez. Mas note que o mais 
//indicado é não usar variáveis globais. 
struct PILHA stack; // declara uma variável global stack que é do tipo struct PILHA 
 
 
/****************************************************************************/ 
 
void init_stack(void) //Função que inicializa a pilha de nome stack 
{ 
 stack.topo = -1; 
} 
 
 
bool stack_empty(void) //bool é um tipo booleano. Uma variável deste tipo pode ser true ou false 
{ 
 if (stack.topo == -1 ) 
 return true; 
 else 
 return false; 
} 
 
 
char pop(void) 
{ 
 char valor; 
 
 if (stack.topo >= 0) 
 { 
 valor = stack.vetp[stack.topo]; 
 stack.topo--; 
 return valor; 
 } 
 else 
 exit(0); //termina o programa, o que é bem radical 
} 
 
 
bool push(int valor) 
{ 
 // Para ter espaco a distancia entre os dois topos tem que ser maior que 1 
 if (stack.topo < MAX-1) 
 { 
 // Se tem espaco entao aloca o elemento e incrementa o topo 
 ++stack.topo; 
 stack.vetp[stack.topo] = valor; 
 
 return(true); //é um sinal que diz que ocorreu bem o empilhamento 
 } 
 else 
 
 return(false); 
} 
/****************************************************************************/ 
bool palindroma(char palavra[ ]) 
{ 
 int i, 
 tam = strlen(palavra), //conta o número de caracteres de palavra. Não conta o caracter nulo !!! 
 meio = tam / 2; //calcula o meio da palavra 
 bool ehImpar; //armazena true, se a palavra tem um no. ímpar de caracteres e false, caso contrário 
 
 if (tam % 2 == 0) //testa se o tamanho da palavra é par 
 ehImpar = false; 
 else 
 ehImpar = true; 
 
 if (meio <= 0) 
 return false; // é falso que palavra é palíndrome. Sai da função e retorna false. 
 
 init_stack(); // inicializa pilha 
 
 for (i = 0; i < meio; i++) // empilha metade da palavra de entrada 
 push(palavra[i]); // envia para a função push cada palavra[i] 
 
 if (ehImpar == true) // se é impar entao pula mais um caracter 
 i++; 
 
 while (i < tam) 
 { 
 if (pop() != palavra[i]) /* desempilha com pop() e compara com o resto da string de entrada */ 
 return(false); /* sinaliza que nao eh palindrome e sai da função */ 
 i++; 
 } 
 
 return(true); /* sinaliza que eh palindroma */ 
} 
 // Programa principal 
int main( ) { 
 char palavra[64]; 
 bool resposta; 
 
 while (true) /* serao lidas varias palavras */ 
 { 
 
 cout << "\n Programa para checar se uma palavra eh Palindroma\n\n"; 
 
 cout << "Digite uma palavra (ENTER termina programa). Utilize apenas minusculas: "; 
 gets(palavra); 
 
 if (palavra[0] == '\0') 
 break; 
 
 resposta = palindroma(palavra); 
 if (resposta == true) 
 cout << "\nA palavra " << palavra << "eh palindroma " << endl; 
 else 
 cout << "\nA palavra " << palavra << " nao eh palindroma " << endl; 
 
 } 
 
} 
 
4. Escreva um programa em C++ que calcule o valor de uma expressão em notação polonesa reversa 
(notação pós-fixa). Considere as 4 operações e que se está trabalhando apenas com dígitos (valores 
de 0 a 9). 
 
Obs: Na notação polonesa reversa o operador é posto após os operandos. Assim sendo, não é mais 
necessária a utilização de parênteses, já que não há ambiguidade, como na notação infixa. 
 
Ex: Notação infixa : (2 + 3)* 5 Notação Polonesa Reversa: 23+5* 
 Notação infixa : 2 + 3*5 Notação Polonesa Reversa: 235 
 
Gabarito : 
 
#include <cctype> // para usar isdigit 
#include <iostream> 
#include <cstdlib> 
 
using namespace std; 
 
#define MAX 50 
 
struct PILHA { 
 int topo; 
 int vetp[MAX]; 
}; 
 
 
struct PILHA stack; // declara uma variável global stack que é do tipo struct PILHA/****************************************************************************/ 
 
void init_stack(void) //Função que inicializa a pilha de nome stack 
{ 
 stack.topo = -1; 
} 
 
 
/****************************************************************************/ 
bool stack_empty(void) //bool é um tipo booleano. Uma variável deste tipo pode ser true ou false 
{ 
 if (stack.topo == -1 ) 
 return true; 
 else 
 return false; 
} 
 
 
 
 
 
 
 
 
 
 
/****************************************************************************/ 
 
int pop(void) { 
 int valor; 
 
 if (stack.topo >= 0) 
 { 
 valor = stack.vetp[stack.topo]; 
 stack.topo--; 
 return valor; 
 } 
 else 
 // Retorna -1 se pilha esta vazia 
 return(-1); 
} 
 
/****************************************************************************/ 
 
int push(int valor) 
{ 
 // Para ter espaco a distancia entre os dois topos tem que ser maior que 1 
 if (stack.topo < MAX-1) 
 { 
 // Se tem espaco entao aloca o elemento e incrementa o topo 
 ++stack.topo; 
 stack.vetp[stack.topo] = valor; 
 
 // Retorna 1 para indicar sucesso 
 return(1); //é um sinal que diz que ocorreu bem o empilhamento 
 } 
 else 
 // Retorna ZERO para indicar pilha cheia 
 return(0); 
} 
 
 
/****************************************************************************/ 
/****************************************************************************/ 
// Programa principal 
 
 
int main() 
{ 
 char exp[MAX], c; 
 int i, a, b, erro; 
 
 erro = false; 
 
 while (true) 
 { 
 
 
 cout << "CALCULADORA PARA EXPRESSOES EM FORMA POS-FIXADA \n\n"; 
 
 cout << "Digite uma expressao (ENTER termina programa): "; 
 gets(exp); 
 
 if (exp[0] == '\0') //testa se é o caracter nulo logo de cara 
 { 
 cout << "FIM DO PROGRAMA." << endl; 
 break; //sai da main 
 } 
 
 init_stack(); //chama a função para inicilizar a pilha 
 
 for (i=0; exp[i] != '\0'; i++) 
 { 
 c = exp[i]; //Pega um caracter do vetor exp 
 if (isdigit(c)) //testa se o conteúdo de c é dígito 
 push(c-48); //converte de caracter para dígito fazendo c - 48 e então, empilha o resultado de c-48 
 else 
 { 
 
 a = pop(); //desempilha um valor e joga em a 
 b = pop(); //desempilha outro valor e joga em b 
 switch (c) 
 { 
 case '+' : push(a+b); 
 break; 
 
 case '*' : push(a*b); 
 break; 
 
 case '-' : push(a-b); 
 
 case '/' : if (a == 0) //não dá para fazer divisão por zero 
 { 
 erro = true; 
 cout << "Divisao por zero !"; 
 } 
 else 
 push(b/a); 
 break; 
 
 default : cout << "Caracter invalido !"; 
 erro = true; 
 } // fim do switch 
 } // fim else 
 } // fim do for 
 
 if (erro == false) 
 cout << "Resultado : " << pop() << endl; 
 else 
 cout << "\nERRO ! NAO FOI POSSIVEL OBTER O RESULTADO !" << endl; 
 
 system("pause"); 
 } 
}