Dada una expresión con solo ‘}’ y ‘{‘. La expresión puede no estar equilibrada. La tarea es encontrar el número mínimo de inversiones de paréntesis para equilibrar la expresión.
Ejemplos:
Input : exp = "}{"
Output : 2
We need to change '}' to '{' and '{' to
'}' so that the expression becomes balanced,
the balanced expression is '{}'
Input : exp = "}{{}}{{{"
Output : 3
The balanced expression is "{{{}}{}}"
La solución discutida en la publicación anterior requiere O (n) espacio adicional. El problema se puede resolver utilizando el espacio constante.
La idea es usar dos variables abrir y cerrar donde, abrir representa el número de paréntesis de apertura desequilibrados y cerrar representa el número de paréntesis de cierre desequilibrados.
Atraviese la string y, si el carácter actual es un corchete de apertura, incremente open . Si el carácter actual es un corchete de cierre, verifique si hay corchetes de apertura desequilibrados ( abierto > 0). En caso afirmativo, disminuya la apertura ; de lo contrario, aumente el cierre , ya que este soporte está desequilibrado.
A continuación se muestra la implementación del enfoque anterior:
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();
// length of expression must be even to make
// it balanced by using reversals.
if (len % 2)
return -1;
// To store number of reversals required.
int ans = 0;
int i;
// To store number of unbalanced opening brackets.
int open = 0;
// To store number of unbalanced closing brackets.
int close = 0;
for (i = 0; i < len; i++) {
// If current bracket is open then increment
// open count.
if (expr[i] == '{')
open++;
// If current bracket is close, check if it
// balances opening bracket. If yes then
// decrement count of unbalanced opening
// bracket else increment count of
// closing bracket.
else {
if (!open)
close++;
else
open--;
}
}
ans = (close / 2) + (open / 2);
// For the case: "}{" or when one closing and
// one opening bracket remains for pairing, then
// both need to be reversed.
close %= 2;
open %= 2;
if (close)
ans += 2;
return ans;
}
// Driver Code
int main()
{
string expr = "}}{{";
cout << countMinReversals(expr);
return 0;
}
Java
// Java program to find minimum number of
// reversals required to balance an expression
class GFG
{
// Returns count of minimum reversals for making
// expr balanced. Returns -1 if expr 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;
// To store number of reversals required.
int ans = 0;
int i;
// To store number of unbalanced opening brackets.
int open = 0;
// To store number of unbalanced closing brackets.
int close = 0;
for (i = 0; i < len; i++)
{
// If current bracket is open then increment
// open count.
if (expr.charAt(i) == '{')
open++;
// If current bracket is close, check if it
// balances opening bracket. If yes then
// decrement count of unbalanced opening
// bracket else increment count of
// closing bracket.
else
{
if (open == 0)
close++;
else
open--;
}
}
ans = (close / 2) + (open / 2);
// For the case: "}{" or when one closing and
// one opening bracket remains for pairing, then
// both need to be reversed.
close %= 2;
open %= 2;
if (close != 0)
ans += 2;
return ans;
}
// Driver Code
public static void main(String args[])
{
String expr = "}}{{";
System.out.println(countMinReversals(expr));
}
}
// This code is contributed by Arnab Kundu
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):
length = len(expr)
# length of expression must be even to
# make it balanced by using reversals.
if length % 2:
return -1
# To store number of reversals required.
ans = 0
# To store number of unbalanced
# opening brackets.
open = 0
# To store number of unbalanced
# closing brackets.
close = 0
for i in range(0, length):
# If current bracket is open
# then increment open count.
if expr[i] == "":
open += 1
# If current bracket is close, check if it
# balances opening bracket. If yes then
# decrement count of unbalanced opening
# bracket else increment count of
# closing bracket.
else:
if not open:
close += 1
else:
open -= 1
ans = (close // 2) + (open // 2)
# For the case: "" or when one closing
# and one opening bracket remains for
# pairing, then both need to be reversed.
close %= 2
open %= 2
if close > 0:
ans += 2
return ans
# Driver Code
if __name__ == "__main__":
expr = "}}{{"
print(countMinReversals(expr))
# This code is contributed by Rituraj Jain
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 expr)
{
int len = expr.Length;
// length of expression must be even to make
// it balanced by using reversals.
if (len % 2 != 0)
return -1;
// To store number of reversals required.
int ans = 0;
int i;
// To store number of unbalanced opening brackets.
int open = 0;
// To store number of unbalanced closing brackets.
int close = 0;
for (i = 0; i < len; i++)
{
// If current bracket is open then increment
// open count.
if (expr[i] == '{')
open++;
// If current bracket is close, check if it
// balances opening bracket. If yes then
// decrement count of unbalanced opening
// bracket else increment count of
// closing bracket.
else
{
if (open == 0)
close++;
else
open--;
}
}
ans = (close / 2) + (open / 2);
// For the case: "}{" or when one closing and
// one opening bracket remains for pairing, then
// both need to be reversed.
close %= 2;
open %= 2;
if (close != 0)
ans += 2;
return ans;
}
// Driver Code
public static void Main(String []args)
{
String expr = "}}{{";
Console.WriteLine(countMinReversals(expr));
}
}
// This code contributed by Rajput-Ji
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)
{
var len = expr.length;
// length of expression must be even to make
// it balanced by using reversals.
if (len % 2)
return -1;
// To store number of reversals required.
var ans = 0;
var i;
// To store number of unbalanced opening brackets.
var open = 0;
// To store number of unbalanced closing brackets.
var close = 0;
for (i = 0; i < len; i++) {
// If current bracket is open then increment
// open count.
if (expr[i] == '{')
open++;
// If current bracket is close, check if it
// balances opening bracket. If yes then
// decrement count of unbalanced opening
// bracket else increment count of
// closing bracket.
else {
if (!open)
close++;
else
open--;
}
}
ans = (close / 2) + (open / 2);
// For the case: "}{" or when one closing and
// one opening bracket remains for pairing, then
// both need to be reversed.
close %= 2;
open %= 2;
if (close)
ans += 2;
return ans;
}
// Driver Code
var expr = "}}{{";
document.write( countMinReversals(expr));
// This code is contributed by noob2000.
</script>
Producción:
2
Complejidad de tiempo: O(N), donde N es la longitud de la string.
Espacio Auxiliar: O(1)