This content originally appeared on DEV Community and was authored by Vinícius Aarão Caldas da Costa
I start to post a serie of algorithms for help us, I learn the code, english and reinforce about this. And I expected to help you and contribute for the community.
This algorithm is to easy to understand because your problem is to easy, but it's a excellent example to see how we can get the solution with simples steps.
The first step is see the problem:
"we’re going to determine whether or not a set of brackets are balanced or not by making use of the stack data structure that we defined in the previous lesson.
Let’s first understand what a balanced set of brackets looks like.
A balanced set of brackets is one where the number and type of opening and closing brackets match and that is also properly nested within the string of brackets." (educative.io)
Examples of Balanced Brackets
{ }
{ } { }
( ( { [ ] } ) )
Examples of Unbalanced Brackets
( ( )
{ { { ) } ]
[ ] [ ] ] ]
What is your first thought to solve this?
My second step to solve problems like this is to put pen to paper (I like to use simple diagrams) every variable that we might use and all data we have (It's similar to solve physics problems).
Show this new example "}]"
Array = ["}", "]"]
We need to compare the caracters and when we see over the examples, It's clarely that we can use the array to compare?
def is_match(p1, p2):
if p1 == "(" and p2 == ")":
return True
elif p1 == "{" and p2 == "}":
return True
elif p1 == "[" and p2 == "]":
return True
else:
return False
def is_paren_balanced(paren_string):
s = Stack()
is_balanced = True
index = 0
while index < len(paren_string) and is_balanced:
paren = paren_string[index]
if paren in "([{":
s.push(paren)
else:
if s.is_empty():
is_balanced = False
break
else:
top = s.pop()
if not is_match(top, paren):
is_balanced = False
break
index += 1
if s.is_empty() and is_balanced:
return True
else:
return False
Our step to declare that is balanced or not is verify the number of the Array (never works in % 2 != 0), and discover if exist a opening brackets for input in our array and find using is_match the closing brackets.
When over the looping, is declared balanced or not.
That's it!
OBS: We need to use the Stack Data Structure. I believe that you know about this methods.
class Stack():
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def is_empty(self):
return self.items == []
def peek(self):
if not self.is_empty():
return self.items[-1]
def get_stack(self):
return self.items
This content originally appeared on DEV Community and was authored by Vinícius Aarão Caldas da Costa
Vinícius Aarão Caldas da Costa | Sciencx (2024-09-24T19:31:00+00:00) Algorithm to determine if brackets are balanced. Retrieved from https://www.scien.cx/2024/09/24/algorithm-to-determine-if-brackets-are-balanced/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.