使表达式平衡所需的最小括号反转数-yiteyi-C++库

给定一个只有“}”和“{”的表达式。该表达式可能不平衡。请找到最小的括号反转数，使表达式平衡。 例如：

null

Input:  exp = "}{"Output: 2We need to change '}' to '{' and '{' to'}' so that the expression becomes balanced, the balanced expression is '{}'Input:  exp = "{{{"Output: Can't be made balanced using reversalsInput:  exp = "{{{{"Output: 2 Input:  exp = "{{{{}}"Output: 1 Input:  exp = "}{{}}{{{"Output: 3

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

一个简单的观察是，只有当括号的总数为偶数时（必须有相等的“{”和“}”）字符串才能平衡 A. 天真的解决方案 是考虑每一个括号和递归计数的倒数，采取两种情况下（i）保持支架，因为它是（ii）逆转支架。如果我们得到一个平衡的表达式，如果到达这里的步数小于到目前为止的最小值，我们将更新结果。该解的时间复杂度为O（2） ^N ).

一 有效解决方案 可以在O（n）时间内解决这个问题。我们的想法是首先去掉表达的所有平衡部分。例如，convert“} {{}} {{{”到“}{{”通过移除突出显示的部分。如果我们仔细观察，我们可以注意到，在移除平衡部分后，我们总是得到一个形式为}…}{…{的表达式，这个表达式包含0个或更多的结束括号，后面是0个或更多的开始括号。形式为“}}..}{{..{”的表达式需要多少个最小反转。设m为闭括号的总数，n为开括号的数目。我们需要⌈m/2⌉ + ⌈n/2⌉ 反转。例如}{{{{需要2+1个反转。以下是上述想法的实施：

C++14

                         // C++ program to find minimum number of                       
                         // reversals required to balance an expression                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
           
                         // Returns count of minimum reversals for making                       
                         // expr balanced. Returns -1 if expr cannot be                       
                         // balanced.                       
                         int                                     countMinReversals(string expr)                       
                         {                       
                                                 int                                     len = expr.length();                       
           
                                                 // length of expression must be even to make                       
                                                 // it balanced by using reversals.                       
                                                 if                                     (len%2)                       
                                                 return                                     -1;                       
           
                                                 // After this loop, stack contains unbalanced                       
                                                 // part of expression, i.e., expression of the                       
                                                 // form "}}..}{{..{"                       
                                                 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]);                       
                                                 }                       
           
                                                 // Length of the reduced expression                       
                                                 // red_len = (m+n)                       
                                                 int                                     red_len = s.size();                       
           
                                                 // count opening brackets at the end of                       
                                                 // stack                       
                                                 int                                     n = 0;                       
                                                 while                                     (!s.empty() && s.top() ==                                     '{'                                     )                       
                                                 {                       
                                                 s.pop();                       
                                                 n++;                       
                                                 }                       
           
                                                 // return ceil(m/2) + ceil(n/2) which is                       
                                                 // actually equal to (m+n)/2 + n%2 when                       
                                                 // m+n is even.                       
                                                 return                                     (red_len/2 + n%2);                       
                         }                       
           
                         // Driver program to test above function                       
                         int                                     main()                       
                         {                       
                                                 string expr =                                     "}}{{"                                     ;                       
                                                 cout << countMinReversals(expr);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         //Java Code to count minimum reversal for                       
                         //making an expression balanced.                       
           
                         import                                     java.util.Stack;                       
           
                         public                                     class                                     GFG                       
                         {                       
           
                                                 // Method count minimum reversal for                       
                                                 //making an expression balanced.                       
                                                 //Returns -1 if expression cannot be balanced                       
                                                 static                                     int                                     countMinReversals(String expr)                       
                                                 {                       
                                                 int                                     len = expr.length();                       
                                   
                                                 // length of expression must be even to make                       
                                                 // it balanced by using reversals.                       
                                                 if                                     (len%                                     2                                     !=                                     0                                     )                       
                                                 return                                     -                                     1                                     ;                       
                                   
                                                 // After this loop, stack contains unbalanced                       
                                                 // part of expression, i.e., expression of the                       
                                                 // form "}}..}{{..{"                       
                                                 Stack<Character> s=                                     new                                     Stack<>();                       
                                   
                                                 for                                     (                                     int                                     i=                                     0                                     ; i<len; i++)                       
                                                 {                       
                                                 char                                     c = expr.charAt(i);                       
                                                 if                                     (c ==                                     '}'                                     && !s.empty())                       
                                                 {                       
                                                 if                                     (s.peek()==                                     '{'                                     )                       
                                                 s.pop();                       
                                                 else                       
                                                 s.push(c);                       
                                                 }                       
                                                 else                       
                                                 s.push(c);                       
                                                 }                       
                                   
                                                 // Length of the reduced expression                       
                                                 // red_len = (m+n)                       
                                                 int                                     red_len = s.size();                       
                                   
                                                 // count opening brackets at the end of                       
                                                 // stack                       
                                                 int                                     n =                                     0                                     ;                       
                                                 while                                     (!s.empty() && s.peek() ==                                     '{'                                     )                       
                                                 {                       
                                                 s.pop();                       
                                                 n++;                       
                                                 }                       
                                   
                                                 // return ceil(m/2) + ceil(n/2) which is                       
                                                 // actually equal to (m+n)/2 + n%2 when                       
                                                 // m+n is even.                       
                                                 return                                     (red_len/                                     2                                     + n%                                     2                                     );                       
                                                 }                       
                                   
                                                 // Driver method                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 String expr =                                     "}}{{"                                     ;                       
                                   
                                                 System.out.println(countMinReversals(expr));                       
                                                 }                       
           
                         }                       
                         //This code is contributed by Sumit Ghosh                       

Python3

                         # Python3 program to find minimum number of                       
                         # reversals required to balance an expression                       
           
                         # Returns count of minimum reversals                       
                         # for making expr balanced. Returns -1                       
                         # if expr cannot be balanced.                       
                         def                                     countMinReversals(expr):                       
           
                                                 lenn                                     =                                     len                                     (expr)                       
           
                                                 # length of expression must be even                       
                                                 # to make it balanced by using reversals.                       
                                                 if                                     (lenn                                     %                                     2                                     ) :                       
                                                 return                                     -                                     1                       
           
                                                 # After this loop, stack contains                       
                                                 # unbalanced part of expression,                       
                                                 # i.e., expression of the form "...."                       
                                                 s                                     =                                     []                       
                                                 for                                     i                                     in                                     range                                     (lenn):                       
                                                 if                                     (expr[i]                                     =                                     =                                     ''                                     and                                     len                                     (s)):                       
           
                                                 if                                     (s[                                     0                                     ]                                     =                                     =                                     '') :                       
                                                 s.pop(                                     0                                     )                       
                                                 else                                     :                       
                                                 s.insert(                                     0                                     , expr[i])                       
                                                 else                                     :                       
                                                 s.insert(                                     0                                     , expr[i])                       
                                   
                                                 # Length of the reduced expression                       
                                                 # red_len = (m+n)                       
                                                 red_len                                     =                                     len                                     (s)                       
           
                                                 # count opening brackets at the                       
                                                 # end of stack                       
                                                 n                                     =                                     0                       
                                                 while                                     (                                     len                                     (s)                                     and                                     s[                                     0                                     ]                                     =                                     =                                     '') :                       
                                                 s.pop(                                     0                                     )                       
                                                 n                                     +                                     =                                     1                       
           
                                                 # return ceil(m/2) + ceil(n/2) which                       
                                                 # is actually equal to (m+n)/2 + n%2                       
                                                 # when m+n is even.                       
                                                 return                                     (red_len                                     /                                     /                                     2                                     +                                     n                                     %                                     2                                     )                       
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
           
                                                 expr                                     =                                     "}}{{"                       
                                                 print                                     (countMinReversals(expr.strip()))                       
           
                         # This code is contributed by                       
                         # Shubham Singh(SHUBHAMSINGH10)                       

C#

                         // C# Code to count minimum reversal for                       
                         // making an expression balanced.                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         class                                     GFG                       
                         {                       
           
                         // Method count minimum reversal for                       
                         // making an expression balanced.                       
                         // Returns -1 if expression cannot be balanced                       
                         public                                     static                                     int                                     countMinReversals(                                     string                                     expr)                       
                         {                       
                                                 int                                     len = expr.Length;                       
           
                                                 // length of expression must be                       
                                                 // even to make it balanced by                       
                                                 // using reversals.                       
                                                 if                                     (len % 2 != 0)                       
                                                 {                       
                                                 return                                     -1;                       
                                                 }                       
           
                                                 // After this loop, stack contains                       
                                                 // unbalanced part of expression,                       
                                                 // i.e., expression of the form "}}..}{{..{"                       
                                                 Stack<                                     char                                     > s =                                     new                                     Stack<                                     char                                     >();                       
           
                                                 for                                     (                                     int                                     i = 0; i < len; i++)                       
                                                 {                       
                                                 char                                     c = expr[i];                       
                                                 if                                     (c ==                                     '}'                                     && s.Count > 0)                       
                                                 {                       
                                                 if                                     (s.Peek() ==                                     '{'                                     )                       
                                                 {                       
                                                 s.Pop();                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 s.Push(c);                       
                                                 }                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 s.Push(c);                       
                                                 }                       
                                                 }                       
           
                                                 // Length of the reduced expression                       
                                                 // red_len = (m+n)                       
                                                 int                                     red_len = s.Count;                       
           
                                                 // count opening brackets at                       
                                                 // the end of stack                       
                                                 int                                     n = 0;                       
                                                 while                                     (s.Count > 0 && s.Peek() ==                                     '{'                                     )                       
                                                 {                       
                                                 s.Pop();                       
                                                 n++;                       
                                                 }                       
           
                                                 // return ceil(m/2) + ceil(n/2) which is                       
                                                 // actually equal to (m+n)/2 + n%2 when                       
                                                 // m+n is even.                       
                                                 return                                     (red_len / 2 + n % 2);                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     Main(                                     string                                     [] args)                       
                         {                       
                                                 string                                     expr =                                     "}}{{"                                     ;                       
           
                                                 Console.WriteLine(countMinReversals(expr));                       
                         }                       
                         }                       
           
                         // This code is contributed by Shrikant13                       

Javascript

                         <script>                       
                                   
                                                 // JavaScript program to find minimum number of                       
                                                 // reversals required to balance an expression                       
           
                                                 // Returns count of minimum reversals for making                       
                                                 // expr balanced. Returns -1 if expr cannot be                       
                                                 // balanced.                       
                                                 function                                     countMinReversals(expr) {                       
                                                 let len = expr.length;                       
           
                                                 // Expressions of odd lengths                       
                                                 // cannot be balanced                       
                                                 if                                     (len % 2)                       
                                                 return                                     -1;                       
           
                                                 // After this loop, stack contains unbalanced                       
                                                 // part of expression, i.e., expression of the                       
                                                 // form "}}..}{{..{"                       
                                                 var                                     s =                                     new                                     Array();                       
                                                 for                                     (let i = 0; i < len; i++) {                       
                                                 if                                     (expr[i] ==                                     '}'                                     && !s.length == 0) {                       
                                                 if                                     (s[s.length - 1] ==                                     '{'                                     )                       
                                                 s.pop();                       
                                                 else                       
                                                 s.push(expr[i]);                       
                                                 }                       
                                                 else                       
                                                 s.push(expr[i]);                       
                                                 }                       
           
                                                 // Length of the reduced expression                       
                                                 // red_len = (m+n)                       
                                                 let red_len = s.length;                       
           
                                                 // count opening brackets at the end of                       
                                                 // stack                       
                                                 let n = 0;                       
                                                 while                                     (!s.length == 0 && s[s.length - 1] ==                                     '{'                                     ) {                       
                                                 s.pop();                       
                                                 n++;                       
                                                 }                       
           
                                                 // return ceil(m/2) + ceil(n/2) which is                       
                                                 // actually equal to (m+n)/2 + n%2 when                       
                                                 // m+n is even.                       
                                                 return                                     (red_len / 2 + n % 2);                       
                                                 }                       
           
                                                 // Driver program to test above function                       
           
                                                 let expr =                                     "}}{{"                                     ;                       
                                                 document.write(countMinReversals(expr));                       
           
                         </script>                       

输出

输出：

时间复杂性： O（n） 辅助空间： O（n）

另一个 有效解决方案 在O（1）即常数空间中求解问题。因为表达式只包含一种类型的括号，所以我们的想法是维护两个变量，以保持左括号和右括号的计数，就像我们在中所做的那样最长有效子字符串的长度 .如果表达式有平衡括号，那么我们减少左变量，否则增加右变量。然后我们只需要返回ceil（左/2）+ceil（右/2）。

C++

                         // C++ program to find minimum number of                       
                         // reversals required to balance an expression                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Returns count of minimum reversals for making                       
                         // expr balanced. Returns -1 if expr cannot be                       
                         // balanced.                       
                         int                                     countMinReversals(string expr)                       
                         {                       
                                                 int                                     len = expr.length();                       
                                   
                                                 // Expressions of odd lengths                       
                                                 // cannot be balanced                       
                                                 if                                     (len % 2 != 0) {                       
                                                 return                                     -1;                       
                                                 }                       
                                                 int                                     left_brace = 0, right_brace = 0;                       
                                                 int                                     ans;                       
                                                 for                                     (                                     int                                     i = 0; i < len; i++) {                       
                                   
                                                 // If we find a left bracket then we simply                       
                                                 // increment the left bracket                       
                                                 if                                     (expr[i] ==                                     '{'                                     ) {                       
                                                 left_brace++;                       
                                                 }                       
                                   
                                                 // Else if left bracket is 0 then we find                       
                                                 // unbalanced right bracket and increment                       
                                                 // right bracket or if the expression                       
                                                 // is balanced then we decrement left                       
                                                 else                                     {                       
                                                 if                                     (left_brace == 0) {                       
                                                 right_brace++;                       
                                                 }                       
                                                 else                                     {                       
                                                 left_brace--;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 ans =                                     ceil                                     (left_brace / 2.0) +                                     ceil                                     (right_brace / 2.0);                       
                                                 return                                     ans;                       
                         }                       
           
                         // Driver program to test above function                       
                         int                                     main()                       
                         {                       
                                                 string expr =                                     "}}{{"                                     ;                       
                                                 cout << countMinReversals(expr);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java Code to count minimum reversal for                       
                         // making an expression balanced.                       
                         import                                     java.util.*;                       
                         public                                     class                                     GFG {                       
           
                                                 // Method count minimum reversal for                       
                                                 // making an expression balanced.                       
                                                 // Returns -1 if expression cannot be balanced                       
                                                 static                                     int                                     countMinReversals(String expr)                       
                                                 {                       
                                                 int                                     len = expr.length();                       
                                                 int                                     ans;                       
                                   
                                                 // Expressions of odd lengths                       
                                                 // cannot be balanced                       
                                                 if                                     (len %                                     2                                     !=                                     0                                     ) {                       
                                                 return                                     -                                     1                                     ;                       
                                                 }                       
                                                 int                                     left_brace =                                     0                                     , right_brace =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < len; i++) {                       
                                                 char                                     ch = expr.charAt(i);                       
                                   
                                                 // If we find a left bracket then we simply                       
                                                 // increment the left bracket                       
                                                 if                                     (ch ==                                     '{'                                     ) {                       
                                                 left_brace++;                       
                                                 }                       
                                   
                                                 // Else if left bracket is 0 then we find                       
                                                 // unbalanced right bracket and increment                       
                                                 // right bracket or if the expression                       
                                                 // is balanced then we decrement left                       
                                                 else                                     {                       
                                                 if                                     (left_brace ==                                     0                                     ) {                       
                                                 right_brace++;                       
                                                 }                       
                                                 else                                     {                       
                                                 left_brace--;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 ans = (                                     int                                     )(Math.ceil((                                     0.0                                     + left_brace) /                                     2                                     )                       
                                                 + Math.ceil((                                     0.0                                     + right_brace) /                                     2                                     ));                       
                                                 return                                     ans;                       
                                                 }                       
           
                                                 // Driver method                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 String expr =                                     "}}{{"                                     ;                       
           
                                                 System.out.println(countMinReversals(expr));                       
                                                 }                       
                         }                       

Python3

                         # Python 3 program to find minimum number of                       
                         # reversals required to balance an expression                       
                         import                                     math                       
           
                         # Returns count of minimum reversals for making                       
                         # expr balanced. Returns -1 if expr cannot be                       
                         # balanced.                       
                         def                                     countMinReversals(expr):                       
                                                 length                                     =                                     len                                     (expr)                       
           
                                                 # Expressions of odd lengths                       
                                                 # cannot be balanced                       
                                                 if                                     (length                                     %                                     2                                     !                                     =                                     0                                     ):                       
                                                 return                                     -                                     1                       
           
                                                 left_brace                                     =                                     0                       
                                                 right_brace                                     =                                     0                       
           
                                                 for                                     i                                     in                                     range                                     (length):                       
           
                                                 # If we find a left bracket then we simply                       
                                                 # increment the left bracket                       
                                                 if                                     (expr[i]                                     =                                     =                                     '{'                                     ):                       
                                                 left_brace                                     +                                     =                                     1                       
           
                                                 # Else if left bracket is 0 then we find                       
                                                 # unbalanced right bracket and increment                       
                                                 # right bracket or if the expression                       
                                                 # is balanced then we decrement left                       
                                                 else                                     :                       
                                                 if                                     (left_brace                                     =                                     =                                     0                                     ):                       
                                                 right_brace                                     +                                     =                                     1                       
           
                                                 else                                     :                       
                                                 left_brace                                     -                                     =                                     1                       
           
                                                 ans                                     =                                     math.ceil(left_brace                                     /                                     2                                     )                                     +                                     math.ceil(right_brace                                     /                                     2                                     )                       
                                                 return                                     ans                       
           
                         # Driver program to test above function                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
           
                                                 expr                                     =                                     "}}{{"                       
                                                 print                                     (countMinReversals(expr))                       
           
                                                 # This code is contributed by ukasp.                       

C#

                         // C# Code to count minimum reversal for                       
                         // making an expression balanced.                       
                         using                                     System;                       
           
                         public                                     class                                     GFG {                       
           
                                                 // Method count minimum reversal for                       
                                                 // making an expression balanced.                       
                                                 // Returns -1 if expression cannot be balanced                       
                                                 static                                     int                                     countMinReversals(String expr)                       
                                                 {                       
                                                 int                                     len = expr.Length;                       
                                                 int                                     ans;                       
                                   
                                                 // Expressions of odd lengths                       
                                                 // cannot be balanced                       
                                                 if                                     (len % 2 != 0) {                       
                                                 return                                     -1;                       
                                                 }                       
                                                 int                                     left_brace = 0, right_brace = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < len; i++) {                       
                                                 char                                     ch = expr[i];                       
                                   
                                                 // If we find a left bracket then we simply                       
                                                 // increment the left bracket                       
                                                 if                                     (ch ==                                     '{'                                     ) {                       
                                                 left_brace++;                       
                                                 }                       
                                   
                                                 // Else if left bracket is 0 then we find                       
                                                 // unbalanced right bracket and increment                       
                                                 // right bracket or if the expression                       
                                                 // is balanced then we decrement left                       
                                                 else                                     {                       
                                                 if                                     (left_brace == 0) {                       
                                                 right_brace++;                       
                                                 }                       
                                                 else                                     {                       
                                                 left_brace--;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 ans = (                                     int                                     )(Math.Ceiling((0.0 + left_brace) / 2)                       
                                                 + Math.Ceiling((0.0 + right_brace) / 2));                       
                                                 return                                     ans;                       
                                                 }                       
           
                                                 // Driver method                       
                                                 public                                     static                                     void                                     Main(String[] args)                       
                                                 {                       
                                                 String expr =                                     "}}{{"                                     ;                       
           
                                                 Console.WriteLine(countMinReversals(expr));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by aashish1995.                       

Javascript

                                                 <script>                       
                                   
                         // JavaScript program to find minimum number of                       
                         // reversals required to balance an expression                       
           
                         // Returns count of minimum reversals for making                       
                         // expr balanced. Returns -1 if expr cannot be                       
                         // balanced.                       
                         function                                     countMinReversals( expr)                       
                         {                       
                                                 let len = expr.length;                       
                                   
                                                 // Expressions of odd lengths                       
                                                 // cannot be balanced                       
                                                 if                                     (len % 2 != 0) {                       
                                                 return                                     -1;                       
                                                 }                       
                                                 let left_brace = 0, right_brace = 0;                       
                                                 let ans;                       
                                                 for                                     (let i = 0; i < len; i++) {                       
                                   
                                                 // If we find a left bracket then we simply                       
                                                 // increment the left bracket                       
                                                 if                                     (expr[i] ==                                     '{'                                     ) {                       
                                                 left_brace++;                       
                                                 }                       
                                   
                                                 // Else if left bracket is 0 then we find                       
                                                 // unbalanced right bracket and increment                       
                                                 // right bracket or if the expression                       
                                                 // is balanced then we decrement left                       
                                                 else                                     {                       
                                                 if                                     (left_brace == 0) {                       
                                                 right_brace++;                       
                                                 }                       
                                                 else                                     {                       
                                                 left_brace--;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 ans = Math.ceil(left_brace / 2) + Math.ceil(right_brace / 2);                       
                                                 return                                     ans;                       
                         }                       
           
                         // Driver program to test above function                       
           
                                                 let expr =                                     "}}{{"                                     ;                       
                                                 document.write(countMinReversals(expr));                       
           
                         </script>                       

输出

时间复杂性 ：O（n）

辅助空间 ：O（1）

我们不需要为左大括号和右大括号维护两个不同的变量，而是可以使用一个临时变量。

遍历数组。对于每个“{”，将temp的值增加1，对于每个“}”，如果temp的值大于0，则将temp的值减少1，否则，将result的值以及temp的值增加1。最后，将temp值的一半添加到结果中。

下面是C++中上述方法的实现。

C++

                         // C++ program to find minimum number of                       
                         // reversals required to balance an expression                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Returns count of minimum reversals for making                       
                         // expr balanced. Returns -1 if expr cannot be                       
                         // balanced.                       
                         int                                     countMinReversals(string s)                       
                         {                       
                                                 int                                     temp=0, res=0, n=s.size();                       
                                                 if                                     (n%2!=0)                       
                                                 return                                     -1;                       
                                                 for                                     (                                     int                                     i=0;i<n;i++){                       
                                                 if                                     (s[i]==                                     '{'                                     )                       
                                                 temp++;                       
                                                 else                                     {                       
                                                 if                                     (temp==0){                       
                                                 res++;                       
                                                 temp++;                       
                                                 }                       
                                                 else                       
                                                 temp--;                       
                                                 }                       
                                                 }                       
                                                 if                                     (temp>0)                       
                                                 res += temp/2;                       
                                                 return                                     res;                       
                         }                       
           
                         // Driver program to test above function                       
                         int                                     main()                       
                         {                       
                         string expr =                                     "}}{{"                                     ;                       
                         cout << countMinReversals(expr);                       
                         return                                     0;                       
                         //This code is contributed by Akansha Mittal                       
                         }                       

JAVA

                         // Java program to find minimum number of                       
                         // reversals required to balance an expression                       
                         import                                     java.util.*;                       
           
                         class                                     GFG {                       
           
                                                 // Returns count of minimum reversals for making                       
                                                 // expr balanced. Returns -1 if expr cannot be                       
                                                 // balanced.                       
                                                 static                                     int                                     countMinReversals(String s) {                       
                                                 int                                     temp =                                     0                                     , res =                                     0                                     , n = s.length();                       
                                                 if                                     (n %                                     2                                     !=                                     0                                     )                       
                                                 return                                     -                                     1                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++) {                       
                                                 if                                     (s.charAt(i) ==                                     '{'                                     )                       
                                                 temp++;                       
                                                 else                                     {                       
                                                 if                                     (temp ==                                     0                                     ) {                       
                                                 res++;                       
                                                 temp++;                       
                                                 }                                     else                       
                                                 temp--;                       
                                                 }                       
                                                 }                       
                                                 if                                     (temp >                                     0                                     )                       
                                                 res += temp /                                     2                                     ;                       
                                                 return                                     res;                       
                                                 }                       
           
                                                 // Driver program to test above function                       
                                                 public                                     static                                     void                                     main(String[] args) {                       
                                                 String expr =                                     "}}{{"                                     ;                       
                                                 System.out.print(countMinReversals(expr));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Rajput-Ji                       

C#

                         // C# program to find minimum number of                       
                         // reversals required to balance an expression                       
                         using                                     System;                       
                         class                                     GFG {                       
           
                                                 // Returns count of minimum reversals for making                       
                                                 // expr balanced. Returns -1 if expr cannot be                       
                                                 // balanced.                       
                                                 static                                     int                                     countMinReversals(                                     string                                     s)                       
                                                 {                       
                                                 int                                     temp = 0, res = 0, n = s.Length;                       
                                                 if                                     (n % 2 != 0)                       
                                                 return                                     -1;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 if                                     (s[i] ==                                     '{'                                     )                       
                                                 temp++;                       
                                                 else                                     {                       
                                                 if                                     (temp == 0) {                       
                                                 res++;                       
                                                 temp++;                       
                                                 }                       
                                                 else                       
                                                 temp--;                       
                                                 }                       
                                                 }                       
                                                 if                                     (temp > 0)                       
                                                 res += temp / 2;                       
                                                 return                                     res;                       
                                                 }                       
           
                                                 // Driver program to test above function                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 string                                     expr =                                     "}}{{"                                     ;                       
                                                 Console.Write(countMinReversals(expr));                       
                                                 }                       
                         }                       
           
                         // This code is contribute by ukasp.                       

Javascript

                         <script>                       
                         // javascript program to find minimum number of                       
                         // reversals required to balance an expression                       
           
                                                 // Returns count of minimum reversals for making                       
                                                 // expr balanced. Returns -1 if expr cannot be                       
                                                 // balanced.                       
                                                 function                                     countMinReversals( s)                       
                                                 {                       
                                                 var                                     temp = 0, res = 0, n = s.length;                       
                                                 if                                     (n % 2 != 0)                       
                                                 return                                     -1;                       
                                                 for                                     (i = 0; i < n; i++) {                       
                                                 if                                     (s.charAt(i) ==                                     '{'                                     )                       
                                                 temp++;                       
                                                 else                                     {                       
                                                 if                                     (temp == 0) {                       
                                                 res++;                       
                                                 temp++;                       
                                                 }                                     else                       
                                                 temp--;                       
                                                 }                       
                                                 }                       
                                                 if                                     (temp > 0)                       
                                                 res += temp / 2;                       
                                                 return                                     res;                       
                                                 }                       
           
                                                 // Driver program to test above function                       
                                                 var                                     expr =                                     "}}{{"                                     ;                       
                                                 document.write(countMinReversals(expr));                       
           
                         // This code is contributed by Rajput-Ji                       
                         </script>                       

输出

时间复杂性： O（n）

辅助空间： O（1）

感谢乌特卡什·特里维迪提出上述方法。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章