Algorithms / C / C++

Parentheses matching problem.

Gallery KodeBinary

Given a set of parentheses (a string expression), we aim to validate those parentheses. Let us see this with some examples.

Input: {()[]}[{}]
Output: True (Valid)
Input: }[]{][
Output: False (Invalid)

We can solve this problem using stack data structure. Here we have taken three sets of braces which are ‘{}’, ‘()’ and ‘[]’.

Algorithm

  1. Check if stack not empty and current bracket character is the match of its starting bracket.
  2. If the current bracket is not a match of top of the stack, then we push the bracket into the pile.
  3. Or if the stack is empty, we push the current bracket into the pile.
  4. If the current bracket is matches with the bracket in the top of the stack, we pop the bracket from the stack.
  5. Once we process all the expressions, the stack left empty. Then the expression is valid; otherwise, the input is invalid.
Insert initial bracket into stack as stack is empty.
In this step, we check the stack top ‘{‘ value with current ‘(‘ as they are not matching parentheses, pushing into the stack.
Third bracket in the expression is match of the top element of stack, so popped out of stack.
Top of stack is not matches with current bracket, so pushing into stack.
Finally all brackets processed in stack left an empty stack at end.

We follow this process until all characters finish in the input expression and see whether stack left with any brackets or not.

Code for this approach is as showing below.

bool isParanthMatch(string inp)
{
    stack<char> st;
    for (int i = 0; i < inp.length(); i++)
    {
        char curr = inp.at(i);
        if (!st.empty())
        {
            if ((st.top() == '{' && curr == '}') ||
                (st.top() == '[' && curr == ']') ||
                (st.top() == '(' && curr == ')'))
            {
                st.pop();
            }
            else
            {
                st.push(curr);
            }
        }
        else
        {
            st.push(curr);
        }
    }
    if (st.empty())
    {
        return true;
    }
    return false;
}

This has a linear runtime complexity (i.e., O(n) where ‘n’ is length of expression). Full code with main function is as follows.

// Output
{()[]}[{}] a Valid Parenthese: 1
}[]{][ a Valid Parenthese: 0

We hope this article helps you understand finding the validity of the parentheses problem. If you know any better approach to solve this problem, please let our readers know by commenting here below. Happy Learning!.