Resolução de questão

[José Weseles Alves]

Bom dia pessoal!

Estou com dificuldades para resolver esta questão:

Vimos no nosso curso que Python já é dotado da estrutura Lista, através de sua classe list. Usamos então as listas predefinidas de Python para implementar Pilhas e Filas. No algoritmo a seguir, P e F são da classe list. P será tratada como uma pilha onde o topo é o último elemento na ordem de leitura; F será tratada como uma fila onde o início é o primeiro elemento inserido na mesma; 
 

Algoritmo

1 - Construir a lista P de números reais (numa quantidade qualquer) lendo do teclado seus itens fornecidos numa única linha;

2 - Escrever P;

3 - Retirar sequencialmente os elementos de P, inserindo-os um a um na fila F;

4 - Escrever F e P.

Fim-Algoritmo.   

Acho que estou complicando o código:

pilha_aux_Numeros =[]
P1 = []
P2 = []
P3 = []
F = []
#n = 1

def Push(n, p = P1):p.append(n)

def Pop(p = P1):return p.pop()

pilha_aux_Numeros = input('Digite os itens separados por vírgula:\n- Números: ')
pilha_aux_Numeros = pilha_aux_Numeros.split(',')

for i in range(len(pilha_aux_Numeros)):
    Push(pilha_aux_Numeros[i],P1)

for i in range(len(pilha_aux_Numeros)):
    P1[i] = Pop(pilha_aux_Numeros)

pilha_aux_Numeros = P1
print('')
print('Pilha P:',P1)
print('')

def tamanhoPilha(p) :
    return len(p)

def ehNumerico(x):
    try:
        teste = float(x)
    except:
        return False
    return True

def indice(pos): #Retorna a posição dos índices um a um no loop/while
    if (pos==1):return '1º'
    print('')  
    if (pos==2):return '2º'   
    if (pos==3):return '3º'   
    if (pos==4):return '4º'   
    if (pos==5):return '5º'   
    else:return '6º'

def Desempilhar(p):
    return p.pop(-1)   

pos=1

while pos<7:
    print (indice(pos)+' item a ser retirado de P inserido em F: ')
   
    item = input('- Número: ')
    pos += 1
    Push(item,P1)
print('')

while tamanhoPilha(P1)>0:
    item = Pop(P1)
    ehNumerico(item),Push(item, pilha_aux_Numeros)
    #else:Push(item, pilha_aux_Numeros)

while tamanhoPilha(pilha_aux_Numeros)>0:
    Push(Desempilhar(pilha_aux_Numeros),P2)
print('')
print('Pilha P atualizada P: ',P2)

while tamanhoPilha(pilha_aux_Numeros )>0:
    Push(Desempilhar(pilha_aux_Numeros ),P3)
print('')
print('Fila F = ',P3)

Digite os itens separados por vírgula:
- Números: 1,2,3,4,5,6

Pilha P: ['6', '5', '4', '3', '2', '1']

1º item a ser retirado de P inserido em F:
- Número: 6

2º item a ser retirado de P inserido em F:
- Número: 5

3º item a ser retirado de P inserido em F:
- Número: 4

4º item a ser retirado de P inserido em F:
- Número: 3

5º item a ser retirado de P inserido em F:
- Número: 2

6º item a ser retirado de P inserido em F:
- Número: 1

(Rodando só dá isso!)

Fico muito grato quem puder tirar essa dúvida... Uma solução mais simples....

[Marcelo Valle (BLOOMBERG/ LONDON)]

Jose, tem como colocar seu codigo num gist? https://gist.github.com/

Ficara mais facil te ajudar

--
--
------------------------------------
Grupo Python-Brasil
http://www.python.org.br/wiki/AntesDePerguntar
 
<*> Para visitar o site do grupo na web, acesse:
http://groups.google.com/group/python-brasil
 
<*> Para sair deste grupo, envie um e-mail para:
python-brasi...@googlegroups.com

---
Você recebeu essa mensagem porque está inscrito no grupo "Python Brasil" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para python-brasi...@googlegroups.com.
Para mais opções, acesse https://groups.google.com/d/optout.

<< ideas don't deserve respect >>

[Linux - Junior Polegato]

Em 25-05-2016 07:52, José Weseles Alves escreveu:
> Bom dia pessoal!
> Estou com dificuldades para resolver esta questão:
> Vimos no nosso curso que Python já é dotado da estrutura Lista,
> através de sua classe list. Usamos então as listas predefinidas de
> Python para implementar Pilhas e Filas. No algoritmo a seguir, P e F
> são da classe list. P será tratada como uma pilha onde o topo é o
> último elemento na ordem de leitura; F será tratada como uma fila onde
> o início é o primeiro elemento inserido na mesma;
> Algoritmo
> 1 - Construir a lista P de números reais (numa quantidade qualquer)
> lendo do teclado seus itens fornecidos numa única linha;
> 2 - Escrever P;
> 3 - Retirar sequencialmente os elementos de P, inserindo-os um a um na
> fila F;
> 4 - Escrever F e P.
> Fim-Algoritmo.
> Acho que estou complicando o código:

> [...]

Olá!

Na pilha cada elemento inserido ocupa a última posição e na
fila ocupa a primeira. Cada elemento retirado de ambas será sempre o último.

Dessa forma, para inserir na pilha usa-se
`pilha.append(elemento)´ e na fila usa-se `fila.insert(0, elemento)´.
Para retirar usa-se `lista.pop()´.

Dito isso, o algoritmo pode ser dado dessa forma:

# 1 - Construir a lista P de números reais em uma linha
P = [float(x) for x in input('Números separados por vírgula: ').split(',')]
# 2 - Mostrar P
print('P:', P)
# Criar F
F = []
# 3.1 - Enquanto tiver elementos em P
while P:
# 3.2 - Retirar o último elemento de P e colocar em F
F.insert(0, P.pop())
# 4 - Mostrar P e F
print('-' * 50)
print('P:', P)
print('F:', F)

--

[]'s

Junior Polegato

[José Weseles Alves]

Olá Junior Polegato!

Nossa como ficou simples e compreensível...

Muito obrigado!

[José Weseles Alves]

Olá Marcelo! Desculpa só vi agora sua mensagem...

O Junior Polegato respondeu e ficou bem simples...
Muito obrigado!

[Renzo Nuccitelli]

Apenas complementando, apesar de não ser pedido e ser um pouco mais avançado, o ideal é que a estrutura de Fila tenha operação de inserção em tempo constante O(1). A lista por ser implementando como array dinâmico levará O(n) para inserir elementos em seu início. Se pensar que vai inserir no início n vezes, isso vai levar O(n**2). 

Nesse caso seria melhor usar deque[0]. Fiz essa menção do curso de Estrutura de Dados que dei na Fatec e inclusive pedi pro pessoal definir uma Fila na unha, com testes automáticos: https://github.com/renzon/estrutura-de-dados/tree/master/aula5. Fica o Java do projeto ;)

Grande abraço,

[0]: https://docs.python.org/3.5/library/collections.html#collections.deque

--

Renzo Nuccitelli

www.python.pro.br

Eu leio email somente uma vez por dia. Se o assunto for urgente, me ligue.

[Juan Lopes]

O Java? Olha o ato falho aí :P

Renzo, não seria mais legal para os alunos aprenderem como construir queues e stacks a partir de arrays estáticos? Digo, por mais que Python proveja arrays dinâmicos e deques, em nem toda situação real isso vai ser o mais apropriado. Posso citar, por exemplo, o fato de Java (seguindo sua indicação :D) exigir boxed types para usar o Deque<T> com tipos primitivos, o que é bastante ineficiente em termos de memória e otimização de cache lines. Com frequência otimizo códigos tendo que construir heaps, deques, etc. customizados usando apenas arrays estáticos.

Não sou professor e entendo muito pouco de didática, além claro de não conhecer seu curso (talvez você fale sobre isso depois). Mas fiquei com a impressão que no curso de estruturas de dados seria interessante abordar como implementar as estruturas com o mínimo de suporte da linguagem. O que você acha?

https://github.com/juanplopes

[Renzo Nuccitelli]

Olá Juan,

TL, DR: Não sei

Na Fatec por ser um curso de tecnólogo por 2 anos, meu maior objetivo era o pessoal entender as estruturas principais e as complexidades de suas operações quais as vantagens e desvantagens das estruturas que costumamos encontrar já implementada nas linguagens. Nesse sentido preferi por explicar como um array dinâmico é criado a partir de um estático.

Obviamente que em alguns casos eu limitei o uso da bibliotecas e outras pedi para implementar na unha estrutura que já existia, como foi o caso de lista duplamente ligada [0]. Mas mesmo assim, aproveite o momento para falar de alguns padrões de projeto e construções em Pyhon que os implementam de maneira distinta.

Acho que para ser pragmático mesmo deveríamos usar o método cientifico: usar cada uma das abordagens em grupos e tirar métricas. Por isso a resposta do resuma: não sei. Apesar disso, os alunos gostaram bastante da abordagem do curso como um todo, sem provas mas com muito código. Ensinei git e eles postavam tudo lá. Ensinei testes e eles já tinham um norte para programar. Dado o exposto, te ajudo de alguma forma com meu ponto de vista?

Abs,

[0] https://github.com/renzon/estrutura-de-dados/tree/master/aula3

PS: Onde escrevi Java leia-se jabá. Estou tendo Java no mestrado e acho que isso está afetando meu cérebro ;).

 

[Alexandre Paloschi Horta]

Pessoal aqui é rápido... eheh! Bom, gostei da solução do Júnior, com o while. Eu acabei usando uma variável auxiliar pro for. Ah, usei o método append na lista F. Tem alguma diferença relevante pro insert?

P = [float(elem) for elem in input('> ').split(',')]                                 

F = []

print(P)

length_P = len(P)

for i in range(length_P):

     F.append(P.pop())

print(F)

print(P)

[Linux - Junior Polegato]

Olá!

Tal como expliquei, sendo F uma fila, cada novo elemento deve entrar na primeira posição, por isso insert(0, elemento). Se usar append(elemento) estará colocando na última posição, então deixa de ser fila e passa a ser pilha.

--
[]'s

Junior Polegato

[Linux - Junior Polegato]

Em 01-06-2016 02:24, Alexandre Paloschi Horta escreveu:
> É, melhor mesmo. Não dá pra presumir que a lista destino está vazia,
> correto?

Independentemente de vazia ou não, insert(0, elem) para fila e
append(elem) para pilha. Mesmo vazia o efeito não é o mesmo:

P = [1, 2, 3]
F = []

1º ciclo:
F.insert(0, P.pop()): F = [3] | P = [1, 2]
F.append(P.pop()): F = [3] | P = [1, 2]

2º ciclo:
F.insert(0, P.pop()): F = [2, 3] | P = [1]
F.append(P.pop()): F = [3, 2] | P = [1]

3º ciclo:
F.insert(0, P.pop()): F = [1, 2, 3] | P = []
F.append(P.pop()): F = [3, 2, 1] | P = []

Entende a diferença?

--

[]'s

Junior Polegato

[Alexandre Paloschi Horta]

Eheh, esquece o que eu falei, Júnior. Madrugada cuidando da minha bebê. Errei mesmo. :D