def is_balanced(text, brackets="〈〉()[]{}"):
opening, closing = brackets[::2], brackets[1::2]
stack = [] # keep track of opening brackets types
for character in text:
if character in opening: # bracket
stack.append(opening.index(character))
elif character in closing: # bracket
if stack and stack[-1] == closing.index(character):
stack.pop() # remove the matched pair
else:
return False # unbalanced (no corresponding opening bracket) or
# unmatched (different type) closing bracket
return (not stack) # no unbalanced brackets
def is_balanced(text):
text = "".join(el for el in text if el in "〈({[]})〉")
while text:
flag = True
for el in "〈〉", "()", "{}", "[]":
if el in text:
text = text.replace(el, "")
flag = False
if flag:
return False
return True
def is_balanced(text, brackets="〈〉()[]{}"):
L = list(map(re.escape, brackets)) # make it safe for a regex
regex = re.compile('|'.join( # O <-> opening, C <-> closing
['{O}[^{B}]*{C}'.format(B=''.join(L),**vars()) for O, C in zip(L[::2], L[1::2])]))
n = "number of substitutions"
while n:
text, n = regex.subn('', text) # remove non-nested/flat balanced parts
return set(brackets).isdisjoint(text) # no [unbalanced] brackets left
s=list(input())
st=[]
for i in range(len(s)):
if s[i]=='(' or s[i]=='{' or s[i]=='[':
st.append(s[i])
continue
if (s[i]==')' or s[i]=='}' or s[i]==']') and st:
if (st[-1]+s[i]=='()') or (st[-1]+s[i]=='{}') or (st[-1]+s[i]=='[]'):
st.pop()
else:
print('no')
exit()
else:
print('no')
exit()
if st==[]:
print('yes')
else:
print('no')
使用保留(不平衡)左括号类型的堆栈的经典解决方案:
在 Python 3 上:
opening
在这种情况下,大括号类型(花括号/方括号/等)由包含所有左括号的列表中的索引表示。closing
在相同的索引处包含相同类型的右括号。例子:
它可能是这样的:
我们删除除括号外的所有字符。接下来,删除所有空括号,直到字符串为空。如果文本不为空并且其中没有空括号,那么我们返回
False
您可以尽可能长地删除平坦(未嵌套)的平衡部分,然后检查文本中是否留下 [unbalanced] 括号:
可以通过栈使用另一种算法,复杂度O(n):