Stack: Check for balanced brackets using stack

Problem Statement:

Given a string that has parenthesis.
You need to check if it is balanced or not.

Example

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

Solution

We will use stack to solve this problem.
We traverse the string and then if we encounter opening braces (‘(‘ or ‘{‘ or ‘[‘) we push into the stack.
When we encounter closing braces (‘)’ or ‘}’ or ‘]’) we pop from the stack, if the popped character is the matching starting bracket.

Solution in C++

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

using namespace std;

bool check_balanced_parenthesis(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_parenthesis(expr))
        cout << "Brackets are Balanced"<<endl;
    else
        cout << "Brackets are Not Balanced"<<endl;
    return 0;
}

Output:

Brackets are Balanced