Как я могу проверить, сбалансированы ли скобки в строке?

Question

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

class Stack:
    def __init__(self):
        self.list = []

    def is_empty(self):
        if len(self.list) == 0:
            return True
        else:
            return False
    def push(self, item):
        self.list.append(item)
    def pop(self):
        return self.list.pop()
    def peek(self):
        return self.list[-1]

def balanced_brackets(text):
    s = Stack()
    opening = '(<'
    closing = ')>'
    mapping = dict(zip(opening, closing))

    for letter in text:
        if letter in opening:
            s.push(mapping[letter])
        elif letter in closing:
            if not s or letter != s.pop():
                return False
    return True

'' '

print(balanced_brackets('(<x>)(())()'))#this test case is correct
print(balanced_brackets('(((((((xyz))))))'))#but this is wrong

'' '

Answer 1

Вы должны проверить свой стек в конце цикла for:

def balanced_brackets(text):
    s = Stack()
    opening = '(<'
    closing = ')>'
    mapping = dict(zip(opening, closing))

    for letter in text:
        if letter in opening:
            s.push(mapping[letter])
        elif letter in closing:
            if s.is_empty() or letter != s.pop():
                return False
    if not s.is_empty():
        return False
    return True

выход

print(balanced_brackets('(<x>)(())()'))
print(balanced_brackets('(((((((xyz))))))'))

True
False

Answer 2

Вы можете использовать объект collections.Counter, чтобы просто посчитать количество присутствующих скобок и сравнить эти числа для определения баланса:

from collections import Counter

cnt = Counter('(((((((xyz))))))')
if cnt['('] != cnt[')']:
    print('unbalanced')

Я думаю, что вы поняли идею и можете ее использовать.