Odwracanie stosu w Pythonie za pomocą rekursji

Question

Zrobiłem kilka pytań praktycznych. Ten musi odwrócić stos bez użycia jakichkolwiek innych struktur danych oprócz innego stosu.

Wiem, że potrzebuję funkcji pomocnika, która dołącza pop-ed liczby, gdy oryginalny stos jest pusty.

Czy ktoś może mnie uruchomić? Utknąłem tutaj

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

Dzięki!

Klasa Stack ma funkcje pop, push i is_empty.

Answer 1

Oto kolejna możliwość, przy użyciu akumulatora i funkcji pomocnika. Używam tylko metod przewidzianych w swojej klasie Stack i żadnych innych struktur danych (takich jak listy Pythona):

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) 

Należy pamiętać, że oryginalny stos będzie pusta na końcu, a przerzucony stos jest zwrócony.

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

następujące prace jeśli stos jest rodowitym lista Python:

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[:] powoduje oryginalny stos być zachowane.

Nie powinno być trudno zmienić to, aby obsłużyć daną klasę Stack.

Answer 4

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

Answer 5

Zakładając brak struktury danych powinien być stosowany nawet nie listy trzymać ostateczny rezultat Oto jeden z możliwych rozwiązań

stosie tutaj by uznać wykaz, który obsługuje następujące funkcje

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

Rozwiązanie 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)] 

Nawet ty możesz kodować bez użycia IsEmpty ot funkcjonalność NotEmpty

Rozwiązanie 2:

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

Uwaga * * Korzystanie Exception o warunkowe sprawdzianów akceptowaną zachowanie w Pythonie, ponieważ nie ma dodany narzut jak w 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) 

Wydajność:

daje

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

Możesz nawet można sobie wyobrazić, wykorzystując fakt, że zamknięcie zachowuje parametr stack w zakresie funkcji rekursywnej, więc nie jest konieczne, aby był parametrem funkcji wewnętrznej. na przykład

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()) 

Albo pozbyć się wszystkich parametrów na funkcji rekurencyjnej, a wątek stos ramka dziękuję:

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