使用堆棧的Python Palindrom程序

Question

我的任務是在Python中想出一個迴文程序。我在這裏做

def isPalindrome(word): 
    for i in range(len(word)//2): 
     if word[i] != word[-1-i]: 
      return False 
    return True 

print (isPalindrome("maam")) #returns TRUE 
print (isPalindrome("madam")) #returns TRUE 
print (isPalindrome("hello")) #returns FALSE 
print (isPalindrome("macdam")) #returns FALSE 
print (isPalindrome("buffalolaffub")) #returns TRUE 
print (isPalindrome("argentina")) #returns FALSE 

現在我的教練希望這個使用Stack s內轉換。任何人都可以幫忙嗎？

這裏的Stack數據結構，我有：

class Stack: 

    def __init__(self): 
     self.items = [] 

    def isEmpty(self): 
     return self.items == [] 

    def push(self, item): 
     self.items.append(item) 

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

    def peek(self): 
     return self.items[len(self.items)-1] 

    def size(self): 
     return len(self.items) 

Answer 1

好，因爲棧是先入後出他們自然逆轉的事情。你可以遍歷字符串，推動前半部分，然後彈出並比較下半部分。

Answer 2

考慮：

tests=["maam", "madam","hello","macdam","buffalolaffub","argentina"] 

地道的Python檢查的字符串是一個迴文是這樣的：

word==word[::-1] # True or False 

所以，你可以打印迴文名單如下：

print [word for word in tests if word==word[::-1]]  

要做到這一點與堆棧，你需要把字符串變成一個列表，然後Python列表/堆棧操作ons可供您使用。這裏是一個小的演示：

def stack_cmp(s1,s2): 
    l1=list(s1) 
    l2=list(s2) 
    if len(l1)!=len(l2): return False 
    while True: 
     try: 
      if l1.pop()!=l2.pop(): return False 
     except IndexError: 
      return True 

print [word for word in tests if stack_cmp(word, word[::-1])] 

的stack_cmp另一種版本，不使用異常：

def stack_cmp(s1,s2): 
    l1=list(s1) 
    l2=list(s2) 
    while l1 and l2: 
     if l1.pop()!=l2.pop(): return False 
    if l1 or l2: return False 
    return True 

然後工作這樣WWAY：

>>> stack_cmp('mmmm','mmmm') 
True 
>>> stack_cmp('mmmm','mmmmm') 
False 

你的老師可能反對使用切片來反轉列表;即，revered_list=orig_list[::-1]。如果是這樣的話，你可以使用這個：

reversed_list=[] 
orig_list_copy=orig_list[:] 
while orig_list_copy: 
    reversed_list.append(orig_list_copy.pop()) # this reverses the list 

這可以作爲一個palidrome檢查一個Stack類：

class Stack(object): 
    def __init__(self,items): 
     self.items=[] 
     for e in items: 
      self.push(e) 

    def push(self,item): 
     self.items.append(item) 

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

    def __repr__(self): 
     return str(self.items) 

    def isPalindrome(self): 
     tr=Stack([]) 
     t=Stack(self.items) 
     while t.items: 
      tr.push(t.pop()) 
     t=Stack(self.items)  
     while t.items and tr.items: 
      c1=t.pop() 
      c2=tr.pop() 
      print c1,c2 
      if c1!=c2: return False 
     return True