Balanced brackets in Python

Brackets are said to be balanced when every opening bracket has a corresponding closing bracket.

svg viewer

Algorithm

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.

1 of 8

Code

We have used the algorithm from the above illustration​ in the code below.

# Function to test balanced brackets
def BalancedBrackets(Str):
# stack for storing opening brackets
stack = []
# Loop for checking string
for char in Str:
# if its opening bracket, so push it in the
# stack
if 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 it
elif char == '}' or char == ')' or char == ']':
if len(stack) == 0:
return False
top_element = stack.pop() # pop
# function to compare whether two
# brackets are corresponding to each other
if not Compare(top_element, char):
return False
# lastly, check that stack is empty or not
if len(stack) != 0:
return False
return True
# Function to check two corresponding brackets
# equal or not.
def Compare(opening, closing):
if opening == '(' and closing == ')':
return True
if opening == '[' and closing == ']':
return True
if opening == '{' and closing == '}':
return True
return False
# Test function
print(BalancedBrackets("{123(456[.768])}"))
Copyright ©2024 Educative, Inc. All rights reserved