Question

Проверка скобочных выражений 1. Напишите программу, которая проверяет правильность скобочного выражения с четырьмя видами скобок: (), [], {} и <>. Все операции со стеком вынесите в отдельный модуль.

Answer 1

Для решения данной задачи, нам понадобится использовать структуру данных "стек". Стек - это упорядоченная коллекция элементов, в которой добавление и удаление элементов происходит только одним концом, называемым "вершиной" стека.

Для начала создадим класс "Stack", который будет представлять собой стек. У этого класса должны быть следующие методы: - `push(item)`: добавление элемента в стек - `pop()`: удаление и возвращение элемента из вершины стека - `peek()`: возврат элемента из вершины стека без его удаления - `is_empty()`: проверка, пуст ли стек - `size()`: получение количества элементов в стеке

class Stack:

def __init__(self):
        self.items = []

def push(self, item):
        self.items.append(item)

def pop(self):
        return self.items.pop()

def peek(self):
        return self.items[-1]

def is_empty(self):
        return len(self.items) == 0

def size(self):
        return len(self.items)

Теперь, чтобы проверить правильность скобочного выражения, можно использовать этот класс. Давайте напишем функцию `check_brackets(expression)`, которая будет принимать на вход скобочное выражение и возвращать True, если все скобки корректно сбалансированы, и False в противном случае.

def check_brackets(expression):
    stack = Stack()
    opening_brackets = '([{<'
    closing_brackets = ')]}>'
    
    for char in expression:
        if char in opening_brackets:
            stack.push(char)
        elif char in closing_brackets:
            if stack.is_empty():
                return False
            
            top_char = stack.pop()
            if opening_brackets.index(top_char) != closing_brackets.index(char):
                return False

return stack.is_empty()

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

Например, можно вызвать функцию `check_brackets("(3+[4-2]*{6/2})")`, и она вернет True, так как все скобки в этом выражении сбалансированы. Но если вызвать функцию `check_brackets("(3+[4-2)*{6/2})")`, она вернет False, так как скобки не сбалансированы.

Разместите этот код в одном модуле и сохраните его с расширением .py. Затем импортируйте этот модуль в другом месте вашей программы, чтобы использовать функцию `check_brackets`.