使用Python中的堆栈检测回文

huangapple go评论78阅读模式
英文:

Palindrome using Stack in Python

问题

我正在尝试使用堆栈来实现回文,但我卡在了下面的代码上。尽管我应该得到'True',但我得到了'False'。你能帮我吗?

from Stack import Stack
import copy

def display(data):
    original = Stack()
    reverse = Stack()
    for i in range(len(data)):
        original.push(data[i])
        
    dat = copy.deepcopy(original)
    
    for i in range(len(data)):
        a = original.pop()
        reverse.push(a)
    
    reverse.disp() # disp() 显示列表形式的元素
    dat.disp()
    if dat == reverse:
        return True
    else:
        return False

print(display('racecar'))
英文:

I am trying to implement palindrome using stack but I am stuck with the code below. While I should get 'True', I am getting 'False'. Can you please help me through?

from Stack import Stack
import copy

def display(data):
    original= Stack()
    reverse= Stack()
    for i in range(len(data)):
        original.push(data[i])
        
    dat=copy.deepcopy( original)
#    print(hex(id(dat)))
#    print(hex(id(original)))
    
    for i in range(len(data)):
        a= original.pop()
        reverse.push(a)
#    original.disp()
    reverse.disp() #disp() shows elements in list form
    dat.disp()
    if dat == reverse:
        return True
        
    else:
        return False
        
print(display('racecar'))

答案1

得分: 1

如果你将单词的前半部分推入栈中,你应该能够逐个比较它们与单词的剩余部分的字母,因为你弹出它们。如果它们全部匹配,你就有一个回文。没有必要手动反转列表(这有点违背使用栈的初衷),也不需要制作副本。这两种方法都会降低效率。关键是区分奇数长度的单词和偶数长度的单词,因为在奇数长度的单词中,你不需要比较中间的字母。

由于你没有提供栈的实现,我将使用一个列表,但你应该能够看到它是如何工作的:

def pali(s):
    stack = []
    mid = len(s)//2

    # 将单词的前半部分推入栈中
    for c in s[:mid]:
        stack.append(c)
 
    # 调整奇数长度单词的中间位置
    if len(s) % 2: 
        mid += 1

    # 弹出栈中的字母并查看单词的剩余部分
    for c in s[mid:]:
        if stack.pop() != c:
            return False

    return True

print(pali("hello")) # False
print(pali("madamimadam")) # True

请注意,这段代码用一个列表模拟了栈的行为。

英文:

If you push the letters from the first half of a word onto the stack, you should be able to compare them to rest of the word letter by letter as you pop them off the stack. If they all match you have a palindrome. There's no need to manually reverse the list (and that kind of defeats the point of using a stack) or make copies. Both hurt the efficiency. The trick is distinguishing words with odd lengths from even lengths, because you don't need to compare the middle letter in odd-length words

Since you didn't provide a stack implementation, I'll just use a list, but you should be able to see how it works:

def pali(s):
    stack = []
    mid = len(s)//2
    
    # push first half of the word onto stack
    for c in s[:mid]:
        stack.append(c)
 
    # adjust mid for odd length words
    if len(s) % 2: 
        mid+=1

    # look at rest of the word while popping off the stack
    for c in s[mid:]:
        if stack.pop() != c:
            return False

    return True
      
print(pali("hello")) # False
print(pali("madamimadam")) # True

答案2

得分: 0

给定@MarkMeyer的答案是如果您想要使用堆栈的正确方法,如果您的输入实际上是Python序列(例如listtuplestr等),则检查回文更紧凑且更高效的方法是使用切片:

def is_palindrome(seq):
    n = len(seq)
    m = n // 2
    q = m + n % 2 - 1
    return seq[:m] == seq[:q:-1]


print(is_palindrome('ciao'))
# False
print(is_palindrome('aboba'))
# True
print(is_palindrome('abooba'))
# True
英文:

Given that @MarkMeyer's answer is the correct way to proceed if you want to make use of stacks, if your input is actually a Python sequence (e.g. a list, tuple, str, etc.) a much more compact and efficient way of checking for palindrome is by using slicing:

def is_palindrome(seq):
    n = len(seq)
    m = n // 2
    q = m + n % 2 - 1
    return seq[:m] == seq[:q:-1]


print(is_palindrome('ciao'))
# False
print(is_palindrome('aboba'))
# True
print(is_palindrome('abooba'))
# True

答案3

得分: -1

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

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

    def push_val(self, data):
        self.items.append(data)

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

my_instance = Stack_structure()
text_input = input('输入字符串...')

for character in text_input:
    my_instance.push_val(character)

reversed_text = ''
while not my_instance.check_empty():
    reversed_text = reversed_text + my_instance.pop_val()

if text_input == reversed_text:
    return True
else:
    return False
英文:
class Stack_structure:
   def __init__(self):
      self.items = []

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

   def push_val(self, data):
     self.items.append(data)

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

my_instance = Stack_structure()
text_input = input('Enter the string... ')

for character in text_input:
   my_instance.push_val(character)

reversed_text = ''
while not my_instance.check_empty():
   reversed_text = reversed_text + my_instance.pop_val()

if text_input == reversed_text:
   return True
else:
return False

huangapple
  • 本文由 发表于 2020年1月6日 02:37:26
  • 转载请务必保留本文链接:https://go.coder-hub.com/59603027.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定