0

Прошу помощи с задачей Стек Max

Нужно реализовать класс StackMax, который поддерживает операцию определения максимума среди всех элементов в стеке. Класс должен поддерживать операции push(x), где x – целое число, pop() и get_max().

Формат ввода В первой строке записано одно число n — количество команд, которое не превосходит 10000. В следующих n строках идут команды. Команды могут быть следующих видов:

push(x) — добавить число x в стек; pop() — удалить число с вершины стека; get_max() — напечатать максимальное число в стеке; Если стек пуст, при вызове команды get_max() нужно напечатать «None», для команды pop() — «error».

Формат вывода Для каждой команды get_max() напечатайте результат её выполнения. Если стек пустой, для команды get_max() напечатайте «None». Если происходит удаление из пустого стека — напечатайте «error».

Python 3.7.9

Я написал почти рабочий код, но не работает самое главное: Значения вставляет, возвращает pop, в стеке последнее число удаляется как и должно. Но в get_max число, которое должно было удалиться, остается и из-за этого неправильные ответы. Можете подсказать, целый день убил...

Вот вывод терминала подтверждает, что в стеке удаляется попом, а в get_max остается.

>>> from stack_max import *
3
push 100
push 200
pop
>>> stack.get_max
'200'

Мой код:

class StackMax:
    def __init__(self):
        self.items = []
        self.get_max = []
 
    def push(self, items):
        self.items.append(items)
        if len(self.items) == 1 or items > self.get_max:
            self.get_max = items
        if len(self.items) == 0:
            self.get_max.append(int(items))
 
    def pop(self):
        if stack.items == 0:
            return 'error'
        removed = self.items.pop()
        if removed == self.get_max:
            self.get_max = self.items[0]
            for value in self.items:
                if value > self.get_max:
                    self.get_max = value
        return removed
        
    def get_max(self):
        if len(self.items) == 0:
            return None
        return print(max(self.items))
 
stack = StackMax()
number = int(input())
answer = []
for _ in range(number):
    input_commands = input().split()
    if input_commands[0] == "push":
        stack.push(input_commands[1])
    if input_commands[0] == "pop":
        if len(stack.items) == 0:
            answer.append('error')
        if len(stack.items) != 0:
            stack.items.pop()
    
    if input_commands[0] == "get_max":
        if len(stack.items) == 0:
            answer.append("None")
        answer.append(stack.get_max)
 
for i in answer:
    if len(i) != 0:
        print(i)

Ошибка теста:

Ввод:
5
push -9
get_max
pop
get_max
get_max

Вывод:
-9
None
-9
None
-9

Правильный ответ:
-9
None
None

Мне кажется, проблема в предпоследнем блоке в моменте answer.append(stack.get_max). Он вставляет тут все подряд, но не удаляет походу.

1
  • get_max надо же вызывать, то есть get_max()
    – CrazyElf
    29 дек 2022 в 18:32

2 ответа 2

0

В коде было много лишнего и неоднозначного

test = """5
push -9
get_max
pop
get_max
get_max""".split('\n')


def input(): # функция переопределена в тестовых целях для замены ручного ввода
    global test
    return test.pop(0)


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

    def push(self, items):
        self.items.append(items)

    def pop(self):
        if len(self.items) == 0:
            return 'error'
        self.items.pop()

    def get_max(self):
        if len(self.items) == 0:
            return None
        return max(self.items)


stack = StackMax()
number = int(input())
answer = []
for _ in range(number):
    input_commands = input().split()
    if input_commands[0] == "push":
        stack.push(int(input_commands[1]))
    elif input_commands[0] == "pop":
        p = stack.pop()
        if p is not None:
            answer.append(p)
    elif input_commands[0] == "get_max":
        answer.append(stack.get_max())

print(*answer, sep='\n')
-9
None
None
1
  • ошибка, говорит нет items.. Traceback (most recent call last): File "f5100def-62fe-4118-a5e8-1c5c014ae202", line 30, in <module> answer.append(stack.get_max()) File "f5100def-62fe-4118-a5e8-1c5c014ae202", line 14, in get_max if len(self.items) == 0: AttributeError: 'StackMax' object has no attribute 'items'
    – Den
    29 дек 2022 в 19:45
0

Благодарю за помощь ребят CrazyElf и Алексей Р.

Решил вот так.

class StackMax:
    def __init__(self):
        self.items = []
        self.g_max = []
 
    def push(self, item):
        if len(self.items) == 0 or item >= self.g_max[-1]:
            self.g_max.append(item)
        self.items.append(item)
 
    def pop(self):
        if len(stack.items) == 0:
            return 'error'
 
        if self.items.pop() == self.g_max[-1]:
            self.g_max.pop()
        
    def get_max(self):
        if len(self.items) == 0:
            return 'None'
        return self.g_max[-1]
 
stack = StackMax()
number = int(input())
answer = []
for _ in range(number):
    input_commands = input().split()
    if input_commands[0] == "push":
        stack.push(int(input_commands[1]))
 
    if input_commands[0] == "pop":
        if stack.pop() == 'error':
            answer.append('error')
        
    if input_commands[0] == "get_max":
        answer.append(stack.get_max())
 
for i in answer:
    print(i)

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.