# Check Matching & Balanced Brackets using Stack

• If we have a string containing different types of brackets which can be

• We have to check if all the brackets are matched & balanced correctly.

• Two brackets are considered to be matching if the an opening bracket i.e.  ( , [ , or  { occurs to the left of a closing bracket i.e. ) , ] , or } of the exact same type.

• A matching pair of brackets will be considered balanced if all enclosing brackets are matched correctly.

• Here are various examples to explain the concept:

# Steps to check matching & balanced brackets

1. Suppose we are given a string which contains different set of brackets. Let s = "{ ( ) } [ ]".

2. Start traversing the string.

3. If opening bracket then push on to the stack.

4. If closing bracket then match it with the bracket on top of the stack (i.e. they should be opening & closing brackets of same type)

5. If matching brackets then pop it from stack.

6. If they are not matching that is bracket on top of stack does not match the currently selected bracket or the stack is empty, it is not a matching pair and the string is not matching & balanced.

7. When the string ends if the stack is empty then the brackets are matching and balanced.

# Source Code - C++

#include <iostream>
#include <stack>
using namespace std;

//function to check matching brackets
int matchingPair(char a, char b)
{
    if(a=='{' && b=='}')
        return 1;
    else
    if(a=='[' && b==']')
        return 1;
    else
    if(a=='(' && b==')')
        return 1;
    else
        return 0;
}

// Main function
int main()
{
    
    stack<char> st;
    string s;
    cout<<"Enter the bracket sequence\n";
    cin>>s;
    
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
            st.push(s[i]);
        } else if (st.empty() || !matchingPair(st.top(),s[i])) {
            cout<<"Not a matching pair\n";
            break;
        } else {
            st.pop();
        }
    }
    
    if(st.empty())
        cout<<"Brackets are balanced and matched\n";
    
    return 0;
}

# Applications

• Used to evaluate mathematical expressions like { ( a + b ) + ( c – d )}.

• In many programming languages also we use brackets to define various blocks in our program. If not balanced the compiler will give an error.