Введение
Балансировка скобок — классическая проблема, часто встречающаяся на собеседованиях по программированию. Задача состоит в том, чтобы определить, сбалансирована ли данная строка скобок. Проблема может распространяться на другие типы скобок, такие как фигурные скобки {}
и квадратные скобки []
. В этом сообщении блога мы рассмотрим простое решение этой проблемы с использованием структуры данных стека в 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'
Балансировка скобок с использованием стека
Мы можем использовать стек для балансировки скобок. Алгоритм следующий:
- Инициализировать новый пустой стек.
- Проведите заданную строку слева направо.
- Если текущий символ является открывающей скобкой
(
, поместите ее в стек. - Если текущий символ является закрывающей скобкой
)
, проверьте, не пуст ли стек. Если это так, струна не сбалансирована. Если он не пуст, извлеките верхний элемент из стека. - После обхода, если стек пуст, строка уравновешивается; в противном случае это не так.
Вот как это выглядит в 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