Strings: Check balanced parenthesis

Problem Statement:

You are given a set of parenthesis and you need to check if the given parenthesis are in correct exp.

Example

Input: “[()]{}[()()]()” 
Output: Balanced

Input: “[(])” 
Output: Not Balanced

Solution

We will be able to solve this problem with the help of stacks.

We will push the current character into the stack if the string is ‘(‘ or ‘{‘ or ‘[‘.

We will pop the current character into the stack if the string is ‘)’ or ‘}’ or ‘]’.

Then after completing the traversal, if there are still some bracket left, then it is not balanced, else they are balanced.

Example:

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <stack>

using namespace std;

bool check_balanced_brackets(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 = "{()}[]"; 
  
    if (check_balanced_brackets(expr)) 
        cout << "Balanced"<<endl; 
    else
        cout << "Not Balanced"<<endl; 
    return 0; 
} 

Output:

Balanced