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

Question

Итак, я изучаю структуры данных и алгоритмы, которые в настоящее время работают со стеками, очередями и декеусами

У меня есть этот вопрос, в котором говорится, что я должен реализовать стек, чтобы проверить, имеет ли данная строка сбалансированные скобки, и мне сказали в вопросе, что строка содержит круглые скобки only, а строка имеет no spaces

Итак, я реализовал свой класс Stack, а затем попытался решить проблему Checking if the Parenthesis balance и выполнил простой тестовый пример '[]' и он возвращает False вместо True, поэтому я не могу обнаружить ошибку в коде.

Ниже представлен мой мыслительный процесс по решению вопроса, чтобы вы могли ясно увидеть, где я мог ошибиться:

1. Сначала я проверил, равна ли длина строки, даже если не верну False

2. Я просматриваю строку и каждый раз, когда я вижу открывающую скобку, я отправляю sh ее в стек

3. Затем, когда я вижу закрывающую скобку, я использую знания стеков, которые LIFO я знаю, что я f теперь я вижу закрывающую скобку, предыдущая должна быть соответствующим открытием, которое было последним элементом, помещенным в стек, поэтому я затем извлекаю его из стека и сохраняю в переменной

4. Затем я проверяю, соответствуют ли они, и если они не соответствуют, я возвращаю False

5. Затем я проверяю, пуст ли стек, тогда я знаю, что нет соответствующей открывающей скобки, которую я возвращаю False

6. Наконец, если l oop закончился без какого-либо возврата, я проверяю, пуст ли стек, я возвращаю True иначе I False

Код ниже

class Stack(object):

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

    def isEmpty(self):

        return self.items == 0

    def get_size(self):

        return len(self.items)


    def push(self, data):

        self.items.append(data)

    def peek(self):

        return self.items[len(self)-1]

    def remove_item(self):

        self.items.pop()


stack = Stack()


def balance_check(s):

    if len(s) % 3 == 0:
        return False


    openings = set('({[')
    matches = set([ ('{', '}') , ('(', ')') , ('[', ']') ])

    for paren in s:

        if paren in openings:
            stack.push(paren)


        else:

            if stack.get_size() == 0:
                return False

            last_open = stack.remove_item()

            if (last_open, paren) not in matches:

                return False

    if stack.get_size() == 0:
        return True


print(balance_check('[]'))

Answer 1

Отличная попытка. Вы были очень близки. Всего пара ошибок или опечаток.

1. remove_item() удалил элемент из списка, но не вернулся.
2. проверка нечетности / четности выполняется % 2 == 1, а не % 3.

class Stack(object):
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == 0
    def get_size(self):
        return len(self.items)
    def push(self, data):
        self.items.append(data)
    def peek(self):
        return self.items[len(self.items)-1]
    def remove_item(self):
        # you were not returning here
        return self.items.pop()

stack = Stack()

def balance_check(s):
    # odd/even check is done like this, not by % 3
    if len(s) % 2 == 1:
        return False

    openings = set('({[')
    matches = set([('{', '}'), ('(', ')'), ('[', ']')])

    for paren in s:
        if paren in openings:
            stack.push(paren)
        else:
            if stack.get_size() == 0:
                return False
            last_open = stack.remove_item()
            if (last_open, paren) not in matches:
                return False

    # simplified return
    return stack.get_size() == 0


print(balance_check('{[]{()}}'))

Вы можете добавить больше быстрых проверок, например:

1. Если строка начинается с закрывающей круглой скобки, вернуть False
2. Если строка заканчивается с открывающей круглой скобкой верните False

Answer 2

Ваш алгоритм неверен, так как это недопустимая строка: "]]]][[[["

вместо этого каждый раз, когда вы видите открытую скобку, вы sh помещаете в стек, закрывающая скобка выскакивает, если длина равна 0 до того, как строка исчерпана, ответ будет «ложным», если длина НЕ равна нулю, когда строка исчерпана, ответ будет «ложным». В противном случае - «истина».