Brackets are said to be balanced when every opening bracket has a corresponding closing bracket.
For this problem, we will use a stack. We will push each opening bracket in the stack and pop the last inserted opening bracket whenever a closing bracket is encountered. If the closing bracket does not correspond to the opening bracket, then we stop and say that the brackets are not balanced.
Remember: Always check that the stack is empty at the end because if it is not, the brackets aren’t balanced.
We have used the algorithm from the above illustration​ in the code below.
# Function to test balanced bracketsdef BalancedBrackets(Str):# stack for storing opening bracketsstack = []# Loop for checking stringfor char in Str:# if its opening bracket, so push it in the# stackif char == '{' or char == '(' or char == '[':stack.append(char) # push# else if its closing bracket then# check if the stack is empty then return false or# pop the top most element from the stack# and compare itelif char == '}' or char == ')' or char == ']':if len(stack) == 0:return Falsetop_element = stack.pop() # pop# function to compare whether two# brackets are corresponding to each otherif not Compare(top_element, char):return False# lastly, check that stack is empty or notif len(stack) != 0:return Falsereturn True# Function to check two corresponding brackets# equal or not.def Compare(opening, closing):if opening == '(' and closing == ')':return Trueif opening == '[' and closing == ']':return Trueif opening == '{' and closing == '}':return Truereturn False# Test functionprint(BalancedBrackets("{123(456[.768])}"))
Free Resources