Палиндром с использованием стека в Python - PullRequest
Новая
       28

Палиндром с использованием стека в Python

0 голосов
/ 05 января 2020

Я пытаюсь реализовать палиндром, используя стек, но я застрял с кодом ниже. Хотя я должен получить «Истину», я получаю «Ложь». Можете ли вы помочь мне через? 

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

Ответы [ 2 ]

1 голос
/ 05 января 2020

Если вы наберете sh букв из первой половины слова в стек, вы сможете сравнивать их с остальной частью слова буква за буквой, когда вытаскиваете их из стека. Если они все совпадают, у вас есть палиндром. Нет необходимости вручную переворачивать список (и это лишает смысла использование стека) или делать копии. Оба вредят эффективности. Хитрость заключается в различении слов с нечетными длинами от четных, потому что вам не нужно сравнивать среднюю букву в словах с нечетной длиной

Поскольку вы не предоставили реализацию стека, я просто буду использовать список, но вы должны увидеть, как это работает: 

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
0 голосов
/ 05 января 2020

Учитывая, что @ MarkMeyer's answer - правильный способ продолжить, если вы хотите использовать стеки, если ваш ввод на самом деле представляет собой последовательность Python (например, list, tuple, str, et c.) Гораздо более компактным и эффективным способом проверки палиндрома является использование нарезки: 

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