英文:
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序列(例如list
,tuple
,str
等),则检查回文更紧凑且更高效的方法是使用切片:
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
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论