Invertir una pila en Python usando recursión

Question

Estoy haciendo algunas preguntas de práctica. Éste necesita invertir una pila sin usar ninguna otra estructura de datos excepto otra pila.

Sé que necesitaré una función auxiliar que agregue los números pop-ed una vez que la pila original esté vacía.

¿Alguien me puede ayudar a empezar? Estoy atascado aquí

def flip_stack(s): 
    if not s.is_empty(): 
     temp = s.pop 
     flip_stack(s) 

Gracias!

La clase Stack tiene pop, push y is_empty funciones.

Answer 1

Aquí hay otra posibilidad, usando un acumulador y una función de ayuda. Sólo estoy usando los métodos proporcionados en su clase Stack, y no hay otras estructuras de datos (como listas de Python):

def flip_stack(s): 
    return flip_stack_helper(s, Stack()) # Stack is your stack class 

def flip_stack_helper(s, t): 
    if s.is_empty(): 
     return t 
    t.push(s.pop()) 
    return flip_stack_helper(s, t) 

Tenga en cuenta que la pila de originales estará vacía al final, y la pila volteada es devuelto.

Answer 2

def reverse(orig, reversel=None): 
    if not reversel: 
     reversel = [] 
    reversel.append(orig.pop()) 
    if orig: 
     reverse(orig, reversel) 
    return reversel 

stack = [1, 2, 3, 4, 5] 
stack = reverse(stack) 
print stack 
[5, 4, 3, 2, 1] 

Answer 3

Las siguientes obras si la pila es una lista de Python orígenes:

def flip(stack): 
    def helper(old_stack, new_stack): 
     if old_stack: 
      new_stack.append(old_stack.pop()) 
      return helper(old_stack, new_stack) 
     else: 
      return new_stack 
    return helper(stack[:], []) 

stack[:] hace que la pila original para ser preservado.

No debería ser difícil modificar esto para manejar su clase dada Stack.

Answer 4

>>> liste = [1, 2, 3, 4, 5] 
>>> liste[::-1] 
[5, 4, 3, 2, 1] 

Answer 5

Suponiendo que no hay estructura de datos debe usarse incluso no lista para sostener el resultado final aquí es una posible solución

La Pila aquí sería considerado una lista que apoya la siguiente función

append(elem) ---- push(elem) 
pop()   ---- pop() 
if <some stack>---- NotEmpty() 

Solución 1:

def flip_stack(s): 
    while True: 
     if s: 
      yield s.pop() 
     else: 
      return 

stack = [1,2,3,4,5] 
revStack = [x for x in flip_stack(stack)] 

Incluso puede codificar sin usar la funcionalidad NotEmpty ot IsEmpty

Solución 2:

def flip_stack(s): 
    while True: 
     try: 
      yield s.pop() 
     except IndexError: 
      return 

Nota * * El uso de Excepción para la comprobación condicional es un comportamiento aceptado en Python ya que no tiene añaden gastos generales como en C++

Answer 6

class Stack(object): 
    def __init__(self,items=[]): 
     self.stack = items 

    def is_empty(self): 
     return not self.stack 

    def pop(self): 
     return self.stack.pop() 

    def push(self,val): 
     self.stack.append(val) 

    def __repr__(self): 
     return "Stack {0}".format(self.stack) 

def flip_stack(stack): 
    def flip_stack_recursive(stack,new_stack=Stack()): 
     if not stack.is_empty(): 
      new_stack.push(stack.pop()) 
      flip_stack_recursive(stack,new_stack) 
     return new_stack 
    return flip_stack_recursive(stack) 


s = Stack(range(5)) 
print s 
print flip_stack(s) 

cede

Stack [0, 1, 2, 3, 4] 
Stack [4, 3, 2, 1, 0] 

Usted podría incluso haga un poco de fantasía usando el hecho de que el cierre mantiene el parámetro stack de flip_stack en el alcance de la función recursiva, por lo que no necesita que sea un parámetro para la función interna. p.ej.

def flip_stack(stack): 
    def flip_stack_recursive(new_stack): 
     if not stack.is_empty(): 
      new_stack.push(stack.pop()) 
      flip_stack_recursive(new_stack) 
     return new_stack 
    return flip_stack_recursive(Stack()) 

O, deshacerse de todos los parámetros de la función recursiva, y su marco de pila de subprocesos se lo agradecerán:

def flip_stack(stack): 
    new_stack = Stack() 
    def flip_stack_recursive(): 
     if not stack.is_empty(): 
      new_stack.push(stack.pop()) 
      flip_stack_recursive() 
    flip_stack_recursive() 
    return new_stack