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

Метод 1: подход на основе стека
Один из наиболее распространенных методов сопоставления скобок — использование стека. Идея состоит в том, чтобы поместить каждую открывающую скобку в стек и извлечь ее, когда встретится закрывающая скобка. Если в конце строки стек пуст, это означает, что все круглые скобки сбалансированы.

def parenthesisMatch(s):
    stack = []
    opening = "({["
    closing = ")}]"

    for char in s:
        if char in opening:
            stack.append(char)
        elif char in closing:
            if not stack or opening.index(stack.pop()) != closing.index(char):
                return False

    return len(stack) == 0

Метод 2: подсчет
Еще один простой подход — отслеживать количество открывающихся и закрывающихся скобок. Мы начинаем с нуля, увеличиваем его для каждой открывающей скобки и уменьшаем для каждой закрывающей скобки. Если счетчик становится отрицательным или не возвращается к нулю в конце, круглые скобки несбалансированы.

def parenthesisMatch(s):
    count = 0

    for char in s:
        if char == "(":
            count += 1
        elif char == ")":
            count -= 1
        if count < 0:
            return False

    return count == 0

Метод 3: подход с использованием регулярных выражений
Регулярные выражения также можно использовать для решения проблемы сопоставления скобок. Мы можем заменить все допустимые пары круглых скобок пустой строкой и проверить, пуста ли полученная строка.

import re
def parenthesisMatch(s):
    while re.search(r'\(\)|\{\}|\[\]', s):
        s = re.sub(r'\(\)|\{\}|\[\]', '', s)

    return len(s) == 0

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

def parenthesisMatch(s):
    if s == "":
        return True

    if s[0] == ")" or s[-1] == "(":
        return False

    opening = 0
    for char in s:
        if char == "(":
            opening += 1
        elif char == ")":
            opening -= 1
            if opening < 0:
                return False

    return opening == 0

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