Check for balanced parenthesis in an expression in C++

In this tutorial, we are going to learn about the problem. The problem is to Check for balanced parenthesis in an expression in C++. Firstly we are going to have an introduction to the problem. We will take a look at different types of parenthesis and learn how to balance them.

Introduction

There are several types of parenthesis like (),[],{}. Checking parenthesis means checking that opening and closing parenthesis have a valid meaning as well as there is an equal number of opening and closing of parenthesis. Just having an equal number of opening and closing brackets do not mean having balanced brackets but there should also be a valid meaning of them.

For example:

Expression 1 – “[(])” This expression is invalid.

Expression 2 – “(()())” This expression is valid.

Expression 3 – “{{}[]}” This expression is valid.

To solve this problem other than this logic we will use a stack. A stack will be used to solve the problem.

The algorithm we will be using is:




  1. Create a stack of character type.
  2. Now traverse the string and checking if there is an open bracket in the string if there is then push it. Else if it is a closing bracket then pop the element and check if it is the matching bracket if it is then fine else parenthesis are unbalanced.
  3. Till the stack is empty perform the steps.

Code

#include<bits/stdc++.h> 
using namespace std; 

bool balance(string expr) 
{ 
    stack<char> s; 
    char x; 
 
    for (int i=0; i<expr.length(); i++) 
    { 
        if (expr[i]=='('||expr[i]=='['||expr[i]=='{') 
        { 
            s.push(expr[i]); 
            continue; 
        } 

        if (s.empty()) 
           return false; 
  
        switch (expr[i]) 
        { 
        case ')': 
            x = s.top(); 
            s.pop(); 
            if (x=='{' || x=='[') 
                return false; 
            break; 
  
        case '}': 
  
            x = s.top(); 
            s.pop(); 
            if (x=='(' || x=='[') 
                return false; 
            break; 
  
        case ']': 

            x = s.top(); 
            s.pop(); 
            if (x =='(' || x == '{') 
                return false; 
            break; 
        } 
    } 
    return (s.empty()); 
} 

int main() 
{
  string expr;
  cout<<"Enter a string : ";
  cin>>expr;
    if (balance(expr)) 
        cout << "Balanced"; 
    else
        cout << "Not Balanced"; 
    return 0; 
}

Input and Output:

Enter a string : {{]]
Not Balanced

Enter a string : [[]]
Balanced

In the above program, we have enter the input and as the string. Then after that function balance is called and it checks according to the above algorithm if the parenthesis are balanced or not.

Conclusion

This program of Check for balanced parenthesis in expression in C++ is shown above. The solution covers concepts like stack, string and stack operation. This solution can be used to solve other problems of balancing of parenthesis.

Also Checkout:


Leave a Reply

Your email address will not be published. Required fields are marked *