PRIMEIRA LISTA DE
EXERCíCIOS -
PRAZO DE ENTREGA: 27/03/2000
(0.5 ponto)
Considere 6 carros de trem numerados de 1 a 6 na entrada do estacionamento
em forma de pilha. É possí vel trocar a ordem dos vagões
para 154632? E para 154623?
(1.0 ponto)
As operações de colocar e tirar os n vagões do
estacionamento podem ser codificadas concisamente usando a letra E para
``empilhar'' (ou colocar um vagão no estacionamento) e D para ``desempilhar''
(ou tirar um vagão). Chamamos uma seqüência de E's e
D's de admissí vel se contém n E's, n D's e as operações
codificadas podem ser realizadas. Por exemplo, a seqüência EDEEEEDDEEEDDDDD
é admissí vel, enquanto a seqüência EDDEEEDD não
é admissí vel. Formule uma regra que permita diferenciar
as seqüências admissí veis das que não são.
(1.5 ponto)
Mostre que é possí vel obter uma permutação
p1, p2,...,pn a partir de 1,2,...,n usando
uma pilha se e somente se não existirem í ndices i,j e k
tais que i < j < k e pk < pi < pj.
Uma cadeia de P pode ser especificada por wcwR, onde w é
uma seqüência de a's e b's e wR é o reverso
de w, ou seja, w lido de trás para frente.
Faça um programa que, dada uma cadeia de caracteres x, determina
se x pertence ou não a P, ou seja, se x é da forma wcwR.
(2.0 pontos)
Escreva um algoritmo, usando pilha, que inverte as letras de cada palavra
de um texto terminado por ``.'', preservando a ordem das palavras. Por
exemplo, dado o texto:
Este exercí cio é muito fácil.
a saí da deve ser
Etse oicí crexe é otium licáf.
(2.0 pontos)
Passe a expressão aritmética abaixo para a notação
pósfixa, indicando para cada caractere lido o conteúdo da
pilha de operadores.
A + B * ((C + D) - (A - E * B))/E - B - D
File translated from TEX by TTH,
version 2.34.
On 19 Mar 2000, 11:36.