MAC-IME-USP CARLOS EDUARDO FERREIRA

SALA 297A TEL.: 3818 6140

E-MAIL cef@ime.usp.br

MONITOR: MARCIO C. CABRAL

MAC 122 - Princípios de Desenvolvimento de Algoritmos

Segundo semestre de 2000

Lista de Exercícios - Pilhas

1. Sejam os interiros 1, 2, 3 e 4 que são lidos nesta ordem para serem colocados numa pilha. Considerando-se todas as possíveis seqüências de operações Empilha e Desempilha decida quais das 24 (4!) permutações possíveis podem ser obtidas como saída da pilha. Por exemplo, a permutação 2, 3, 1, 4 pode ser obtida da seguinte forma: Empilha 1, Empilha 2, Desempilha 2, Empilha 3, Desempilha 3, Desempilha 1, Empilha 4, Desempilha 4.

2. Seja $P$ o seguinte conjunto de cadeis sobre $\{a, b, c\}$:
   
   $$P = \{ c, aca, bcb, abcba, bacab, bbcbb, \ldots\}$$
   
   
   Uma cadeia deste conjunto pode ser especificada por $\alpha c \alpha^{-1}$, onde $\alpha$ é uma seqüência de letras que só contém $a's$ e $b's$ e $\alpha^{-1}$ é o reverso de $\alpha$, ou seja, $\alpha$ lido de trás para frente. Dada uma cadeia $\beta$, faça um programa que determina se $\beta$ pertence ou não a $P$, ou seja, determina se $\beta$ é da forma $\alpha c \alpha^{-1}$ para alguma cadeia $\alpha$.

3. Faça um algoritmo que dado um tabuleiro de xadrez $n \times n$ determina se é possível que um cavalo a partir da posição $(1,1)$ do tabuleiro complete um passeio por todas as $n^2$ posições do tabuleiro em $n^2 -1$ passos válidos. Por exemplo para um tabuleiro $5 \times 5$ uma possível solução do problema seria:

   1	6	15	10	21
   14	9	20	5	16
   19	2	7	22	11
   8	13	24	17	4
   25	18	3	12	23

4. Escreva um algoritmo, usando uma Pilha, que inverte as letras de cada palavra de um texto terminado por ponto (`.') preservando a ordem das palvras. Por exemplo, dado o texto:
   ESTE EXERCÍCIO É MUITO FÁCIL.
   a saída deve serf
   ETSE OICÍCREXE É OTIUM LICÁF.

5. Simule a execução do algoritmo de conversão para a notação posfixa com a expressão aritmética abaixo:
   
   $$(A + B) * D + E / (F + A * D) + C$$
   
   

6. Em que devemos alterar o algoritmo de conversão para notação posfixa a fim de que o algoritmo traduza corretamente expressões que:
   1. possuam exponenciação (que será denotada na expressão pelo símbolo especial . Observe que quando escrevemos $A \ @ \ B \ @ \ C$ pelas regras da aritmética o seu significado é $(A \ @ \ (B \ @ \ C))$.

   2. possuam menos e mais unários. Por exemplo: $-A + B -C$ tem como expressão posfixa $A -B + C -$, e $A - (+C -D) * -E$ tem como expressão posfixa $AC+D-E-*-$.

7. Considerando o algoritmo de conversão para a notação posfixa responda as seguintes perguntas.
   1. Qual é o tamanho máximo que a pilha pode atingir se a expressão a ser traduzida tiver tamanho $n$ (i.e., o numero total de operandos, operadores, e abre e fecha parêntesis na expressão é $n$)?

   2. Qual é a resposta para o item (a) se restringirmos o número de parêntesis na expressão para no máximo 6 (número de pares abre e fecha parêntesis)?

8. Uma outra forma de expressão sem parêntesis que é fácil de ser avaliada é chamada de notação prefixa. Nesta forma de escrever as expressões aritméticas os operadores precedem seus operandos. Por exemplo:

   infixa	prefixa
   $A * B / C$	$/ * A B C$
   $A * (D + C) / B - G$	$- / * A + D C B G$
   $A + B * C - D @ E + A * B$	$+ - + A * B C @ D E * A B$

   Observe que a ordem dos operandos não é alterada passando da notação infixa para a prefixa.
   1. Passe a expressão aritmética do exercício 5 para a notação prefixa.

   2. Escreva um algoritmo que transforma uma expressão na forma infixa para a expressão prefixa correspondente.
   Sugestão: percorra a expressão infixa de trás para a frente.

9. Escreva um algoritmo para transformar uma expressão em notação prefixa para a notação posfixa.