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 exc…


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

@vinycxuz


This content originally appeared on DEV Community and was authored by Vinícius Aarão Caldas da Costa


Print Share Comment Cite Upload Translate Updates
APA

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/

MLA
" » Algorithm to determine if brackets are balanced." Vinícius Aarão Caldas da Costa | Sciencx - Tuesday September 24, 2024, https://www.scien.cx/2024/09/24/algorithm-to-determine-if-brackets-are-balanced/
HARVARD
Vinícius Aarão Caldas da Costa | Sciencx Tuesday September 24, 2024 » Algorithm to determine if brackets are balanced., viewed ,<https://www.scien.cx/2024/09/24/algorithm-to-determine-if-brackets-are-balanced/>
VANCOUVER
Vinícius Aarão Caldas da Costa | Sciencx - » Algorithm to determine if brackets are balanced. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2024/09/24/algorithm-to-determine-if-brackets-are-balanced/
CHICAGO
" » Algorithm to determine if brackets are balanced." Vinícius Aarão Caldas da Costa | Sciencx - Accessed . https://www.scien.cx/2024/09/24/algorithm-to-determine-if-brackets-are-balanced/
IEEE
" » Algorithm to determine if brackets are balanced." Vinícius Aarão Caldas da Costa | Sciencx [Online]. Available: https://www.scien.cx/2024/09/24/algorithm-to-determine-if-brackets-are-balanced/. [Accessed: ]
rf:citation
» Algorithm to determine if brackets are balanced | Vinícius Aarão Caldas da Costa | Sciencx | 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.

You must be logged in to translate posts. Please log in or register.