Algorithm to determine if brackets are balanced

vinycxuz

Vinícius Aarão Caldas da Costa

Posted on September 24, 2024

Algorithm to determine if brackets are balanced

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

@vinycxuz

💖 💪 🙅 🚩
vinycxuz
Vinícius Aarão Caldas da Costa

Posted on September 24, 2024

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related