Balanced parentheses using stack in C++

Check balanced parentheses using stack in C++ with program example.

Problem statement: String of parenthesis is given for example “((())) “ or ({}) etc. and we need to find out if they are balanced. Means, if there are matching pairs or not.

for example, ({}) is balanced parentheses and ((((()) is not a balanced parenthesis.

Algorithm:

  • Traverse the expression string
  • If the current character is a opening bracket or parenthesis e.g. ‘(‘ or ‘{‘ or ‘[‘  then push in the stack.
  • If the current character is a closing bracket e.g ‘)’ or ‘}’ or ‘]’ then  pop a character from  the stack and check if it is a corresponding parenthesis, if matched then pop it from stack.
  • Once, string traversal is complete then check if stack is empty or not. If the stack is empty parenthesis are balanced.

 

Time Complexity: O(n) – traverse string of n length.

Space complexity O(n) – Due to Stack

 

Program for bracket matching using stack in C++

This program for parentheses matching using stack in C++ example will handle strings and expressions. Multiple test cases are given after the program.


#include<stack>//Include STL stack

/*
*Program to check balanced parentheses
using stack in C++
*/

#include<iostream>
using namespace std;

class BalancedParenthesisChecker{
public:
      bool isParenthesisBalanced(char s[]){

            //Char STL stack
            stack<char> Stack;
            int i=0;

            /* Traverse the given string expression
            to check matching brackets */

            while(s[i])
            {
                  /*If the s[i] is a opening bracket then
                  push it to Stack*/

                  if( s[i]=='(' || s[i]=='{' || s[i]=='[' )
                  {
                        Stack.push(s[i]);
                  }
                  /* If s[i] is a opening bracket then
                  *get top character from stack and match it
                  *to the current character if match
                  *found then pop it from Stack else
                  *return false*/

                  if( s[i]==')' || s[i]=='}' || s[i]==']' )
                  {
                        if( Stack.empty() || !isEqual(Stack.top(),s[i]) )
                        {
                              return false;
                        }
                        else
                        {
                              //Corresponding brackets matched
                              //pop it from stack
                              Stack.pop();
                        }
                  }
                  i++;
            }


            /*If Stack is empty then parenthesis
            are balanced or else not balanced
            */

            return Stack.empty();
      }

private:
      bool isEqual(char c1, char c2){

            if( c1=='(' && c2==')' )
                  return true;
            else if(c1=='{' && c2=='}')
                  return true;
            else if(c1=='[' && c2==']')
                  return true;
            else
                  return false;
      }
};


/* Test program */

int main()
{
      char str[50];
      BalancedParenthesisChecker cheker;


      cout<<"Enter parenthesis expression:"<<endl;
      cin.getline(str,50);

      bool isBalanced = cheker.isParenthesisBalanced(str);

      if(isBalanced){
            cout<<"Balanced"<<endl;
      }else{
            cout<<"Not Balanced"<<endl;
      }    

      return 0;

}

Test Cases:

Input: “({})”
Output: Balanced

Input: “(((((((“
Output: Not Balanced

Input: “” // empty string
Output: Balanced

Input: “5x+(2/5+[3/a])”
Output: Balanced

Input: “Hello(world)!!!”
Output: Balanced