Задача про скобки.

Супер распространенная задача со скрининг-собеседований, которую я встречала уже не раз.

На вход подается строка, состоящая из круглых скобок. Выведите True, если скобки вложены правильно и False, если нет.

Например, если входная строка (()()(())), то ответ должен быть True.

А если ()), то False.

Это базовая задача на алгоритмы и решается она за один проход по строке (O(n)). Идея здесь следующая: нужно завести переменную-стек, которая будет хранить состояние скобки на i-том шаге и в зависимости от состояния принимать решение о том, валидная строка или нет.

Вот видео с более подробным описанием решения.

Я видела варианты, в которых люди пишут свой класс для стеэка, но в качестве стека сработает и обычный список, если использовать только методы append() и pop().

Вот возможное решение, которое мне нравится:

 if_balanced(string):
    stack = []
    for i in string:
        if i == "(":
            stack.append(i)
        elif i == ")":
            if len(stack) == 0:
                return False
            stack.pop()
    if stack:
        return False
    return True
print(if_balanced("()()())"))

Можете решить ее самостоятельно. 🐠