使用栈实现的Python回文程序

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

现在我的老师希望我把这个程序改成使用栈的方式。有没有人能帮我一下？

这是我现在的栈数据结构：

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的列表/栈操作了。这里有一个简单的演示：

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  

它的工作方式是这样的：

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

这个实现了一个栈类，并且可以检查回文：

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