再帰を使用してPythonでスタックを反転する

Question

私はいくつかの練習問題をしています。これは、他のスタックを除く他のデータ構造を使用せずにスタックをリバースする必要があります。

元のスタックが空になったらポップアップ番号を追加するヘル​​パ関数が必要になることは知っています。

誰かが私を始められますか？私はここにこだわっている

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

ありがとう！

スタッククラスはpop,pushおよびis_emptyの関数を持ちます。

Answer 1

アキュムレータとヘルパー関数を使用する別の方法があります。

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) 

は、元のスタックが最後に空になることに注意してください、と裏返しスタックは次のとおりです。私はあなたのStackクラスで提供された方法、および（例えばPythonのリストなど）がない他のデータ構造を使用しています戻ってきた。何のデータ構造を想定していない

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

次作品のスタックは、ネイティブの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[:]は、元のスタックが保存されます。

与えられたStackクラスを処理するためにこれを変更するのは難しくありません。

Answer 4

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

Answer 5

は、ここでも、最終的な結果を保持するために表示されませ使用しなければならない一つの可能​​な解決策は、ここではスタックは、以下の機能

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

をサポートしてリストと考えられる

です

解決策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)] 

使用しないでコードすることもできますisEmpty OT NotEmpty機能

解決方法2：

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

注* *それは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) 

のように無添加のオーバーヘッドを持っていないとの条件付きチェックするための例外を使用すると、Pythonで受け入れられた行動であります

収量

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

クロージャがstackのパラメータをflip_stackのままにして再帰関数のスコープに入れているという事実を利用して、少し面白くなります。だから、それを内部関数のパラメータにする必要はありません。例えば

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

あるいは、再帰関数のすべてのパラメータを取り除くと、あなたのスレッドのスタックフレームはあなたに感謝します：

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