Stack: Given an expression, get the minimum bracket reversal to make the expression balanced

Problem Statement:

You are given an expression with “{” and “}” and might be balanced.

Find the minimum number of bracket reversal to make the expression balanced.

Example:

Input: "{{"

Output: 1

We need to make 1 reversal.

Solution Explanation:

Solution is very simple.

For every open bracket, check the closing bracket and then remove those brackets.

Then check all the open brackets that are needed to be swapped.

Hence the total numbers of brackets needs to be swapped is half.

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

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

int solution(string s) 
{

    int result = 0;
    stack<char> stack;

    for(int i=0;i<s.length();i++)
    {
        if(s[i]=='[')
        {
            stack.push(s[i]);
        }
        if(s[i]==']' && stack.size()!=0 && stack.top()=='[')
        {
            stack.pop();
        }
    }
    
    result = stack.size();

    if( result%2 == 0)
        return result/2;
    else
        return (result+1)/2;
}

int main()
{
    string expr = "[[";
    cout << solution(expr);
    return 0;
}

Output

1