Введение

Балансировка скобок — классическая проблема, часто встречающаяся на собеседованиях по программированию. Задача состоит в том, чтобы определить, сбалансирована ли данная строка скобок. Проблема может распространяться на другие типы скобок, такие как фигурные скобки {} и квадратные скобки []. В этом сообщении блога мы рассмотрим простое решение этой проблемы с использованием структуры данных стека в Python.

Понимание стеков

Стек — это структура данных «последним пришел — первым обслужен» (LIFO). В Python список можно использовать как стек, где мы можем использовать метод append() для операции push и метод pop() для операции извлечения.

stack = []
stack.append('a')  # push 'a' onto the stack
stack.append('b')  # push 'b' onto the stack
print(stack.pop())  # pop and print the top of the stack: 'b'

Балансировка скобок с использованием стека

Мы можем использовать стек для балансировки скобок. Алгоритм следующий:

  1. Инициализировать новый пустой стек.
  2. Проведите заданную строку слева направо.
  3. Если текущий символ является открывающей скобкой (, поместите ее в стек.
  4. Если текущий символ является закрывающей скобкой ), проверьте, не пуст ли стек. Если это так, струна не сбалансирована. Если он не пуст, извлеките верхний элемент из стека.
  5. После обхода, если стек пуст, строка уравновешивается; в противном случае это не так.

Вот как это выглядит в Python:

def is_balanced(s):
    stack = []
    for char in s:
        if char == '(':
            stack.append(char)
        elif char == ')':
            if not stack:
                return False
            stack.pop()
    return len(stack) == 0

Расширение на другие типы скобок

Приведенный выше алгоритм можно легко расширить для обработки других типов скобок. Нам просто нужно помещать закрывающую скобку в стек всякий раз, когда мы видим открывающую скобку, а затем проверять, соответствует ли вершина стека текущему символу для каждой закрывающей скобки.

def is_balanced(s):
    stack = []
    brackets = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in brackets.values():  # Opening bracket.
            stack.append(brackets[char])
        elif char in brackets.keys():  # Closing bracket.
            if not stack or stack.pop() != char:
                return False
    return len(stack) == 0

Заключение

Уравновешивание круглых скобок — это распространенная проблема на собеседовании по программированию, которая проверяет ваше понимание структур данных стека. Это отличный пример того, как стеки можно использовать для решения задач, связанных с сопоставлением пар или поддержанием определенного порядка. Помните, чем больше вы практикуетесь, тем лучше вы будете определять, когда и как использовать эти фундаментальные структуры данных в своих решениях. Удачного кодирования!

P.S. Хотите еженедельные задачи и новости по кодированию Python? Подпишитесь на рассылку, чтобы получать их прямо в свой почтовый ящик: https://weeklypython.substack.com/welcome