DEV Community 👩‍💻👨‍💻

Cover image for Optimized Balanced Paranthesis solution in Python.
Anshika Bhatnagar
Anshika Bhatnagar

Posted on

Optimized Balanced Paranthesis solution in Python.

Problem Statement:
Given an expression string, write a python program to find whether a given string has balanced parenthesis or not.

Sample Test Case :
Input: '([{}])'
Output: 'Yes'

Although, you have seen many solutions to this problem. For example, using stack, using a queue, and even linked list and
using some graph algorithms too. Here, I am sharing a very straightforward and understandable strategy to solve the balanced parenthesis problem.

We can solve it by using the string's replace method.
Let begin.

string = input()

First, we will take the input string contains a series of parentheses.

> n=-1
> while len(s)!=n:
>    n=len(s)
>    s=s.replace('()','')
>    s=s.replace('[]','')
>    s=s.replace('{}','')
> if len(s)==0:
>    print("Balanced")
> else:
>    print("Imbalanced")

We will run the loop till length of string and n becomes equal. Inside loop, we will take string length in n so that n can store the past length. Now, we will try to replace matching brackets like [], {}, () if they are present in string with empty string. After that again, string length will be compared with past length n.

This will become equal when there will be no more matching brackets. And this condition can arise in 2 cases :

  1. When the string was balanced and finally it becomes an empty string due to constant replacement.
  2. When the string is imbalanced and there are no more brackets to be replaced.

If we get an empty string in the output, then we have got a balanced parenthesis string, else we got an imbalanced string.

Hope this answer helps you in becoming a better competitive programmer. Feel free to ask any questions in the comment section and keep coding guys:)

Top comments (2)

Collapse
 
amanpandya1162 profile image
Aman Pandya

Great approach 👌 Keep blogging

Collapse
 
bhatnagaranshika02 profile image
Anshika Bhatnagar Author

Thank you so much.

🌚 Life is too short to browse without dark mode