Problem Statement:
You are given a string consisting of “{” and “}”.
You need to find the minimum number of inversions needed to balance the expression.
Example
Input: "}{" Output: 2 We need to change '}' to '{' and '{' to '}'. Then the expression becomes balanced '{}'
Solution
The solution is very simple.
First step is to remove all the balanced brackets from the expression.
Example: “}{{}}{“, now remove “{{}}”, you are left with “}{” i.e unbalanced brackets.
If we have “m” number of closing brackets and “n” number of opening brackets.
The reversals required are ⌈m/2⌉ + ⌈n/2⌉.
The time complexity is O(n)
Solution in C++
#include <vector> #include <algorithm> //visit www.ProDeveloperTutorial.com for 450+ solved questions #include <iostream> #include <string> #include <stack> using namespace std; int return_minimum_reversal(string expr) { int len = expr.length(); // if the length is not even, then // the expression is not balanced if (len%2) return -1; stack<char> s; for (int i=0; i<len; i++) { if (expr[i]=='}' && !s.empty()) { if (s.top()=='{') s.pop(); else s.push(expr[i]); } else s.push(expr[i]); } int reduced_len = s.size(); int n = 0; while (!s.empty() && s.top() == '{') { s.pop(); n++; } return (reduced_len/2 + n%2); } int main() { string expr = "}{"; cout <<"The minimum reversal needed is "<< return_minimum_reversal(expr)<<endl; return 0; }
Output:
The minimum reversal needed is 2