Lista de Exercícios - Pilhas

Prévia do material em texto

Lista de exerc´ıcios - Pilhas
Marcos Fagundes Caetano
Abril 2018
1 Exerc´ıcios
1. Implemente a pilha descrita abaixo:
Listing 1: stack.h
typedef struct{
int top;
int size;
int *elements;
} t_stack;
t_stack* create_stack(int size);
bool full_stack(t_stack* stack);
bool empty_stack(t_stack* stack);
int top_stack(t_stack* stack);
void push(t_stack* stack , int element );
int pop(t_stack* stack);
void free_stack(t_stack* stack);
2. Escreva um programa que leia um inteiro N, e empilhe todos os seus d´ıgitos
em uma pilha, que inicialmente estava vazia. O que devera´ acontecer,
considerando que os d´ıgitos foram empilhados da esquerda para direita,
se todos os elementos da pilha forem retirados e colocados na sa´ıda do
programa?
3. Escreva um programa que empilhe todos os caracteres de cada strings e
retorne a sequeˆncia gerada pelas operac¸o˜es POP ate´ que a pilha esteja
vazia.
(a) Estruturas
(b) Dados
(c) Universidade
1
(d) Brasilia
4. Escreva um programa que utilize uma pilha para listar, em ordem decres-
cente, todos os nu´meros primos de 1 a 1000. DICA: Entre 1 e 1000
existem exatos 168 nu´meros primos..
5. Agora, utilize uma pilha para listar os nu´meros primos de 1 a 1000, obtidos
na questa˜o anterior, mas agora em ordem crescente.
6. Escreva um programa que utilize uma pilha para maximizar um nu´mero,
quando este for maior em sua forma reversa.
Exemplo
input: 123456789 output: 987654321
7. Escreva um programa que receba um inteiro N e retorne sua representac¸a˜o
bina´ria.
8. Utilizando uma pilha e´ poss´ıvel verificar se uma expressa˜o e´ balanceada,
verificando os seus delimitadores. O processo e´ simples, quando encon-
trar delimitador esquerdo([), empilhe-o, e quando encontrar um delimi-
tador direito(]), desempilhe um elemento da pilha e compare se os dois
sa˜o pares([]). No fim do processo a pilha precisa estar vazia para que a
expressa˜o seja balanceada. Agora e´ sua vez, escreva um programa que
dada uma sequeˆncia de caracteres retorne 1, caso esta seja balanceada, ou
0, caso contra´rio.
(a) {[()[]]()}
(b) {[(]}
(c) {[()([{}()()]})]}
(d) {[()][()()]()}
9. (APLICAC¸A˜O) Escreva um programa que leia N e M, depois leia 2
strings, a primeira com N caracteres, e a segunda com M caracteres.
A primeira string e´ composta por uma sequeˆncia de comandos do tipo
P(empilhe o pro´ximo caracter da segunda string) e S(desempilhe um el-
emento da pilha), e a segunda string e´ uma palavra qualquer. Por fim
retorne a sequeˆncia gerada depois de realizar as operac¸o˜es, descritas na
primeira string, na segunda string. Na˜o e´ necessa´rio esvaziar a pilha para
o resultado. DICA: Utilize uma varia´vel auxiliar para navegar na
segunda string
2
Exemplo
input:
14 10
PPSPSSPSPSPPSS
estruturas
output: steruut
(a) 14 10
PPSPSSPSPSPPSS
Estruturas
(b) 10 12
PPSPPSSPSP
Universidade
(c) 6 3
PPSPSS
unb
10. (APLICAC¸A˜O) Escreva um programa que dada determinada inter-
pretac¸a˜o de uma string retorne a sequeˆncia gerada pelas operac¸o˜es de
POP em uma pilha, que inicialmente deve estar vazia. Ao encontrar o
comando PUSH seu programa deve empilhar o PRO´XIMO cara´cter da
string
(a) A = PUSH e * = POP.
EAS*Y*QUE***ST***IO*N***
(b) P = PUSH e Z = POP.
SPSABPEEZZCEPUABPRPTZEZZPUPTZZPSPAPRZZZ
(c) T = PUSH e Z = POP.
ZZZTSABTOTDEVBTATDZZZZZZ
Fonte: Sedgewick, Exercise 4.6. Princeton.
11. (APLICAC¸A˜O) Imagine uma sequeˆncia(X) de 0 a 9 em ordem(0 1 2 3 4 5
6 7 8 9). Suponha enta˜o que exista uma sequeˆncia(Y) formada de diversos
P(pushes) e S(pops). Enta˜o os comandos da sequeˆncia Y sa˜o aplicados aos
d´ıgitos da sequeˆncia X. Os P’s empilham o pro´ximo elemento da sequeˆncia
X, e os S desempilha um elemento da pilha na sa´ıda. Desta forma, qual ou
quais das opc¸o˜es abaixo na˜o podera´ acontecer? (Em outras palavras, qual
das permutac¸o˜es abaixo na˜o e´ poss´ıvel ser obtida utilizando uma pilha)
DICA: observe a ordem que os elementos sa˜o empilhados para
poder serem refletidos na sa´ıda.
(a) 4 3 2 1 0 9 8 7 6 5
(b) 4 6 8 7 5 3 2 9 0 1
3
(c) 2 5 6 7 4 8 9 3 1 0
(d) 1 4 7 9 8 6 5 3 0 2
(e) Todas as sequeˆncias sa˜o poss´ıveis.
Fonte: http://www.cs.princeton.edu/courses/archive/spr01/cs126/exercises/adt.html.
12. (APLICAC¸A˜O) Escreva um programa que leia N e duas strings com
N caracteres e determine a sequeˆncia de operac¸o˜es necessa´rias, utilizando
uma pilha inicialmente vazia, para tornar a primeira string igual a se-
gunda. Utilize I para representar operac¸a˜o de push e R para a
operac¸a˜o de POP. Nos exemplos abaixo sempre sera´ poss´ıvel chegar a
uma resposta.
Exemplo
input:
4
e t d a
d a t e
output: IIIRIRRR
(a) 4
e t d a
d a t e
(b) 6
a b d c b a
a b c b a d
(c) 6
a b c d b a
d a b c b a
Fonte: Problem 1063 URI, Rails Again... Tracing Movements.
13. (APLICAC¸A˜O) Utilizando uma pilha e´ poss´ıvel maximar um nu´mero(X)
de N d´ıgitos, para um nu´mero(Y) com (N - M) d´ıgitos, com 1 <M <N
(Ou seja M d´ıgitos sera˜o removidos do nu´mero original X). Para isto, veja
o algor´ıtimo descrito abaixo:
(a) Inicie uma pilha vazia;
(b) Comece a percorrer os d´ıgitos do nu´mero X, da esquerda para direita;
(c) Se a sua pilha estiver vazia, empilhe o pro´ximo d´ıgito;
(d) Caso a sua pilha na˜o esteja vazia. Verifique se pro´ximo digito do
nu´mero X(vamos chama-lo de x1) e´ maior do que o primeiro elemento
4
da pilha(vamos chama-lo de y1) e ainda se nu´mero de d´ıgitos
restante no nu´mero X(ou seja, o nu´mero de d´ıgitos a frente
do x1) + o nu´mero de elementos da pilha for maior que ou
igual a (N - M) enquanto essa afirmac¸a˜o for verdadeira desempilhe
y1, por fim, empilhe o x1.
(e) Por fim, desempilhe todos os u´ltimos (N - M) elementos da pilha em
uma string, e use novamente este pilha para reverter a ordem dos
d´ıgitos.
(f) Para printar o nu´mero, tome cuidado para o nu´mero de d´ıgitos na˜o
exceder (N - M).
Implemente o algor´ıtimo descrito acima e obtenha o nu´mero maximizado
dos valores abaixo. Cada caso de teste e´ composto por N e M, seguido de
um nu´mero X, com N d´ıgitos. E o retorno deve conter (N - M) d´ıgitos:
(a) 4 2
3759
(b) 6 3
123123
(c) 7 4
1000000
(d) 7 3
1001234
(e) 6 2
103759
Fonte: Problem 1084 URI, Erasing and Winning.
5
2 Gabarito
1.
2. O nu´mero deve ser impresso em ordem reversa.
3. As palavras devem ser impressa em ordem reversa.
4. Algorithm of Sieve of Eratosthenes
5.
6.
7. Obtenha o modulo de N por 2, depois divida N por 2. Enquanto N for
maior do que 0.
8. (a) Sim.
(b) Na˜o.
(c) Na˜o.
(d) Sim.
9. (a) steruut
(b) nvie
(c) bnu.
10. (a) S
(b) ESTRUTURAS
(c) DADOS
11. C e D
12. (a) IIIRIRRR
(b) IRIRIIRIRIRR
(c) IIIIRIIRRRRR
13. (a) 79
(b) 323
(c) 100
(d) 1234
(e) 3759
6