Home » Data Structure

Check for balanced parentheses by using Stacks (C++ program)

Check for balanced parentheses in C++: In this tutorial, we will learn how to check for balanced parentheses by using stack using C++ program implementation? By Shivi Saxena Last updated : July 31, 2023

Mathematical calculations can sometimes give incorrect and varied results. To overcome this problem we should use balanced brackets.

Balanced brackets

Balanced brackets are those who have a closing bracket corresponding to each of its opening bracket and in respective order. Here, I am considering square brackets [ ], circular brackets ( ) and curly braces { } as parentheses.

How to check for balanced parentheses by using stacks?

The stack is a type of data structure in which any data inserted is considered to be added on top of first entered data and any data deleted or removed from the data layer structure is deleted from the top only; thus this data structure works on the principle of LIFO (Last In First Out).

First, we make the user enter the number of test cases.Then for each corresponding test case we, call a function named balanced parentheses(). This function allows declaring a stack which can store datatype char. Then, the user is made to enter a string, and then it iterates by the length of string and whenever it approaches an opening bracket, that bracket is inserted (pushed i.e. push function)to the top of the stack. Whenever it comes across a closing bracket, the top element of the stack is deleted( or popped i.e pop function) with a corresponding opening bracket(as one opening and one corresponding closing bracket give empty Stack). While iterating through the length of the string, if it encounters any character other than the brackets(either opening or closing), then it won't affect our stack in any way.

In the end, the whole string has been iterated by its length times, then for the correct case our stack must be empty if it is not, then the brackets in the string entered are not balanced.

Remeber the following examples:

    ( ) : balanced brackets
    ) ( : unbalanced brackets
    { ( ) ( ) } : balanced brackets

See, in expression [(3+5)(12)] the brackets are correctly placed and give the result as 96.

Whereas in {[65-1))]2} the two closing brackets aren't balanced with corresponding opening circular brackets and use of such terms should be taken care of while solving complex mathematical equations.

C++ program to check for balanced parentheses by using stacks

//Updated by Anshuman Singh

#include <iostream> //main header file
#include <stack>
using namespace std;

void balance_parentheses();

int main()
{
    int t;
    cout << "Enter number of test cases:";
    cin >> t;

    for (int i = 0; i < t; i++) {
        //calling of function for checking of brackets
        balance_parentheses();
    }

    return 0;
}

void balance_parentheses()
{
    stack<char> a;
    string s;
    cout << "Enter string may or may not containing parentheses:";
    cin >> s;

    int flag = 0; //flag is an arbitrary variable

    for (int i = 0; i < s.length(); i++)
    //for length of the string calculated by number of letters
    {
        if (s[i] == '{' || s[i] == '[' || s[i] == '(') {
            //push function to enter terms in a stack
            a.push(s[i]);
            flag = 1;
        }
        if (!a.empty()) {
            if (s[i] == '}') {
                if (a.top() == '{')
                // top of the stack
                {
                    a.pop();
                    //pop function to delete terms from the top of array
                    continue;
                }
                else
                    break;
            }
            if (s[i] == ']') {
                if (a.top() == '[') {
                    a.pop();
                    continue;
                }
                else
                    break;
            }
            if (s[i] == ')') {
                if (a.top() == '(') {
                    a.pop();
                    continue;
                }
                else
                    break;
            }
        }
        else {
            break;
        }
    }

    if ((a.empty()) && (flag == 1))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

Output

Enter number of test cases:2 
Enter string may or may not containing parentheses:}[])] 
NO 
Enter string may or may not containing parentheses:[]{}()
YES