0 / 0 / 0
Регистрация: 01.11.2022
Сообщений: 28
1

Задача Стек - Max

29.12.2022, 19:46. Показов 2678. Ответов 7

Author24 — интернет-сервис помощи студентам
Прошу помощи с задачей Стек 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».

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

Вот вывод терминала подтверждает, что в стеке удаляется попом, а в get_max остается..
Код
>>> from stack_max import *
3
push 100
push 200
pop
>>> stack.get_max
'200'

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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)
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.12.2022, 19:46
Ответы с готовыми решениями:

Реализовать стек с поддержкой функций pop(), push(), max()
Реализовать стек с поддержкой функций pop(), push(), max(). Входные данные Последовательность...

Даны векторы a и b , состоящие из семи компонентов. Найти max(max(Ai), max(Bi), max(¦Ai-Bi¦), max(Ai+Bі),1)
Даны векторы a и b , состоящие из семи компонентов. Найти max(max(Ai), max(Bi), max(¦Ai-Bi¦),...

Задача со стеками. В первый стек поместить четные числа в порядке неубывания, во второй стек поместить нечетные
Даны четыре стека.Два первых стека пустые,а в двух других находятся натуральные числа.В первый...

9. Найти максимальный элемент в массиве a1.an, используя соотношение (метод деления пополам) max (a1.an)=max (max (a1.an/2), max (an/2+1, an)
Помогите пожалуйста решить задачу.

7
2429 / 1471 / 633
Регистрация: 01.11.2021
Сообщений: 2,269
29.12.2022, 19:57 2
Если можно каждый раз max() вызывать, то:
Python
1
2
def get_max(self):
    return max(self.items, default=None)
1
0 / 0 / 0
Регистрация: 01.11.2022
Сообщений: 28
29.12.2022, 20:35  [ТС] 3
Вот там пример, как вводятся комынды:

Код
[B]Ввод	
8
get_max
push 7
pop
push -2
push -1
pop
get_max
get_max
Код
Вывод
None
-2
-2
Добавлено через 5 минут
Alexarh, Вот в тестах, как и было:
Ввод:
5
push -9
get_max
pop
get_max
get_max

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

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

Тут проблема в том, что не удаляется после pop. Видишь, -9 выходит, даже после удаления..

Добавлено через 8 минут
Вот:
Код
>>> from stack_max import *
3
push 300               
push 200
get_max 
300
Добавлено через 8 минут
Мне кажется, проблема в этом блоке в моменте answer.append(stack.get_max).
Он вставляет тут все подряд, но не удаляет походу.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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)
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
36588 / 20318 / 4218
Регистрация: 12.02.2012
Сообщений: 33,619
Записей в блоге: 13
29.12.2022, 21:05 4
Alexarh, здесь проблема не в этом. Понятно, что можно вызвать max. Нужно обеспечить получение max за константное (не зависимое от размера стека) время. Функция max этого не обеспечивает.
2
0 / 0 / 0
Регистрация: 01.11.2022
Сообщений: 28
29.12.2022, 23:26  [ТС] 5
Решил так если что:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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)
0
2429 / 1471 / 633
Регистрация: 01.11.2021
Сообщений: 2,269
29.12.2022, 23:55 6
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class StackMax:
    def __init__(self):
        self.items = []
        self.max_elements = []
 
    def push(self, item):
        if not self.items:
            self.max_elements.append(item)
        else:
            self.max_elements.append(max(item, self.max_elements[-1]))
        self.items.append(item)
 
    def pop(self):
        if stack.items == 0:
            return 'error'
        self.max_elements.pop()
        return self.items.pop()
 
    def get_max(self):
        if self.max_elements:
            return self.max_elements[-1]
        return None
 
 
stack = StackMax()
number = int(input())
answer = []
for _ in range(number):
    command, *element = input().split()
    res = getattr(stack, command)(*element)
    answer.append(res)
print(*answer, sep='\n')
Добавлено через 6 минут
Только pop() добавляет элемент в любом случае.
1
Модератор
Эксперт функциональных языков программированияЭксперт Python
36588 / 20318 / 4218
Регистрация: 12.02.2012
Сообщений: 33,619
Записей в блоге: 13
30.12.2022, 09:27 7
Цитата Сообщение от Alexarh Посмотреть сообщение
Только pop() добавляет элемент в любом случае.
- а он должен убирать, а не добавлять...
0
2429 / 1471 / 633
Регистрация: 01.11.2021
Сообщений: 2,269
30.12.2022, 10:03 8
Catstail, я имел ввиду, что добавляет элемент, который удаляем из стека, в итоговый результат, в список answer.
0
30.12.2022, 10:03
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.12.2022, 10:03
Помогаю со студенческими работами здесь

Вычислить произведение Max(A) Max(B), где Max(A) (Max(B)) - максимальный элемент в одномерной матрице
Напишите процедуру на языке VBA для вычисления произведения Max(A) Max(B) , где Max(A) (Max(B))...

Задать значения вещественным элементам массивов A(6),B(3),C(10) и вычислить Y=max(max(A),max(B),max(C)
Задать значения вещественным элементам массивов A(6),B(3),C(10) и вычислить...

Даны различные действительные числа a, b, c, d. Найти max (max(a, b), max(a, c), max(a, d)
Даны различные действительные числа a, b, c, d. Найти max (max(a, b), max(a, c), max(a, d)).

Даны действительные числа A, B, C. Получить max(a,a+b)+max(a,b+c,a+b) \ 1+max(ab,bc)+max(a+bc,15,ac)
Всем привет)Помогите пожалуйста написать в С++ Даны действительные числа A, B, C. Получить...

Заданные действительные a, b. получить max (a, 2b) + max (2a-b, b) определив и использовав функцию max (x, y) - макс. 2
Заданные действительные a, b. получить max (a, 2b) + max (2a-b, b) определив и использовав функцию...

Найти max значение в каждой группе чисел и max из полученных max
Заданы три группы чисел 10, 20, 50 100, 200, 75 A, B, C Найти max значение в каждой группе...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru