Count the Reversals

 Count the Reversals- Data Structures and Algorithms

Given a string S consisting only of opening and closing curly brackets '{' and '}' find out the minimum number of reversals required to make a balanced expression

Input
The first line of input contains an integer T, denoting the number of test cases. Then T test cases
follow. The first line of each test case contains a string S consisting only of { and }.

Output
Print out minimum reversals required to make S balanced. If it cannot be balanced, then print -1

Examples
Input
4
}{{}}{{{
{{}}}}
{{}{{{}{{}}{{
{{{{}}}}

Output
3
1
-1
0

Solution:

For better understanding of this code,you should Check Parenthesis Checker

#include <bits/stdc++.h>

using namespace std;

int main()

{

    //code

    int t;

    cin >> t;

    while (t--)

    {

        string s;

        cin >> s;

        if (s.length() % 2 != 0)

            cout << "-1" << endl;

        else

        {

            stack<char> stk;

            int c1 = 0;

            int c2 = 0;

            for (int i = 0; i < s.length(); i++)

            {

                char ch = s[i];

                if (ch == '{')

                {

                    stk.push(ch);

                    c2++;

                }

                else if (ch == '}' and !stk.empty() and stk.top() == '{')

                {

                    stk.pop();

                    c2--;

                }

                else

                {

                    c1++;

                }

            }

            if (c1 % 2 != 0)

                //checking odd even

                c1 = (c1 / 2) + 1;

            //odd then add 1 else remain same

            else

                c1 = c1 / 2;

            if (c2 % 2 != 0)

                //checking odd or even

                c2 = (c2 / 2) + 1;

            //odd then add 1 else remain same

            else

                c2 = c2 / 2;

            cout << c1 + c2 << endl;

        }

    }

    return 0;

}