Стек ваш нахер не нужОн

[scif_yar]

Задача на корректные скобки
https://leetcode.com/problems/valid-parentheses/

Я ее решил, но ужасающе неэфективно и через жопу, а оказывается это
https://neerc.ifmo.ru/wiki/index.php?title=Правильные_скобочные_последовательности

и даже на олимпиадах для школоты такое есть
https://vos.olimpiada.ru/upload/files/Arhive_tasks/2010-2011/final_tasks/new-cut/iikt/tasks-iikt-9-11-tur1-final-2010-11.pdf

но

но решение
https://leetcode.com/problems/valid-parentheses/solutions/3399077/easy-solutions-in-java-python-and-c-look-at-once-with-exaplanation/
https://leetcode.com/problems/valid-parentheses/solutions/2411675/very-easy-100-fully-explained-c-java-python-js-python3/

--
class Solution(object):
def isValid(self, s):
# Create a pair of opening and closing parrenthesis...
opcl = dict(('()', '[]', '{}'))
# Create stack data structure...
stack = []
# Traverse each charater in input string...
for idx in s:
# If open parentheses are present, append it to stack...
if idx in '([{':
stack.append(idx)
# If the character is closing parentheses, check that the same type opening parentheses is being pushed to the stack or not...
# If not, we need to return false...
elif len(stack) == 0 or idx != opcl[stack.pop()]:
return False
# At last, we check if the stack is empty or not...
# If the stack is empty it means every opened parenthesis is being closed and we can return true, otherwise we return false...
return len(stack) == 0

---
До меня вообще не доходит.

То есть вот код, вот шаги - а логика в голове не возникает.

Comments

[elglin]

Я бы тут посоветовал обратиться немного к абстрактной теории про языки 4 уровней:
1) Регулярные или автоматные (разбираются конечным автоматом)
2) Стековые (разбираются конечным автоматом со стеком)
3) разбираются машиной Тьюринга с ограниченной лентой
4) разбираются машиной Тьюринга вообще

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

Второй момент, что рекурсия - это тоже стек. Многие рекурсивные алгоритмы при наличии стека можно превратить в итеративные (кабы не почти все).
Простейшая ситуация с очередью - это обход дерева в ширину (как обход в глубину - для стека). Очередь возникает часто в графовых алгоритмах, том же OSPF, если я правильно помню. Ее же часто можно использовать в алгоритмах скользящего окна (там часто бывает нужен deque, но нередко не для покладки с обеих сторон, а для посмотра на конечный элемент с обеих сторон).

Ну и вот все такое. На самом деле, из однопроходных алгоритмов естественным образом вылезают многие полезные структуры данных - а все остальные из сортировки и поиска.
Ну ты понял, первые три тома Кнута.

[thagastan]

И "Математическую логику" С.Клини. А до неё неплохо первую книжку его же - "Метаматематика"...

[antontsau.livejournal.com]

логика простая как грабли. Открываем скобку? записываем на бумажке что именно открылось и идем дальше. Закрываем скобку? проверяем по этой бумажке, что последняя открытая такого же типа, и запись стираем. Не совпало (оказался другой тип, или вообще ничего нет) - вываливаем апшипку. Добрались до конца строки и на бумажке как раз ничего не осталось - вываливаем успех.

Это даже не олимпиада для школоты а регулярная задача для 8го класса. Хотя лично бы я это все делал влопп, симулируя стек вручную а не используя какие-то там готовые стековые конструкции и прочие классы. Впрочем можно и стек, на асме 8080, там специальные стековые инструкции есть.

[scif_yar]

>>логика простая как грабли. Открываем скобку? записываем на бумажке что именно открылось и идем дальше. Закрываем скобку? проверяем по этой бумажке, что последняя открытая такого же типа, и запись стираем.
-
А бля. А я то же самое сделал на строках - но редактирование строки работает в разы медленнее стека.
Можно и на массиве было сделать, точнее на list \ списке - или даже и на массиве, запихивая в него и из него вынимая, просто на стеке, похоже, быстрее.