0

我的任务是用 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

现在我的导师希望使用Stacks 转换它。有人可以帮忙吗？

这是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)
4

2 回答 2

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

这可以用作带有回文检查器的 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
于 2013-02-08T00:05:08.343 回答
0

好吧，既然堆栈是先进后出的，他们自然会颠倒事情。您可以遍历字符串，推动前半部分，然后弹出并比较后半部分。

于 2013-02-07T22:36:27.863 回答