Dada una string S de tamaño N que consta de ‘(‘ , ‘)’ y ‘$’ , la tarea es verificar si la string dada se puede convertir en una secuencia de paréntesis balanceada reemplazando cada aparición de $ con ) o ( .
Una secuencia de paréntesis equilibrada es una secuencia en la que cada paréntesis de apertura «(« tiene un paréntesis de cierre correspondiente «)» .
Ejemplos:
Entrada: S = “()($”
Salida: Sí
Explicación: Convierta la string en una secuencia de paréntesis balanceada:()()().Entrada: S = “$()$(“
Salida: No
Explicación: Los reemplazos posibles son “(((((“, “(())(“, “)(()(“, “)()((“ , ninguno de los cuales está equilibrado, por lo que no se puede obtener una secuencia de paréntesis equilibrada.
Enfoque: el problema anterior se puede resolver mediante el uso de una pila . La idea es verificar si todo ) se puede equilibrar con ( o $ y viceversa. Siga los pasos a continuación para resolver este problema:
- Almacene la frecuencia de “(“ , “)” y “$” en variables como countOpen , countClosed y countSymbol respectivamente.
- Inicialice una variable ans como 1 para almacenar el resultado requerido y una pila stack_1 para verificar si todos los «)» se pueden equilibrar con «(« o $ .
- Recorra la string S usando la variable i y haga lo siguiente:
- Si el carácter actual S[i] es «)» , si stack_1 está vacío, entonces establezca ans en 0 , de lo contrario extraiga el carácter de stack_1 .
- De lo contrario , empuje el carácter S[i] a stack_1 .
- Invierta la string S y siga el mismo procedimiento para comprobar si todos los «(« se pueden equilibrar con «)» o «$» .
- Si el valor de countSymbol es menor que la diferencia absoluta de countOpen y countClosed , establezca ans en 0 . De lo contrario, equilibre el paréntesis adicional con los símbolos. Después de equilibrar si countSymbol es impar , configure ans como 0 .
- Después de los pasos anteriores, imprima el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if the string
// can be balanced by replacing the
// '$' with opening or closing brackets
bool canBeBalanced(string sequence)
{
// If string can never be balanced
if (sequence.size() % 2)
return false;
// Declare 2 stacks to check if all
// ) can be balanced with ( or $
// and vice-versa
stack<char> stack_, stack2_;
// Store the count the occurrence
// of (, ) and $
int countOpen = 0, countClosed = 0;
int countSymbol = 0;
// Traverse the string
for (int i = 0;
i < sequence.size(); i++) {
if (sequence[i] == ')') {
// Increment closed bracket
// count by 1
countClosed++;
// If there are no opening
// bracket to match it
// then return false
if (stack_.empty()) {
return false;
}
// Otherwise, pop the character
// from the stack
else {
stack_.pop();
}
}
else {
// If current character is
// an opening bracket or $,
// push it to the stack
if (sequence[i] == '$') {
// Increment symbol
// count by 1
countSymbol++;
}
else {
// Increment open
// bracket count by 1
countOpen++;
}
stack_.push(sequence[i]);
}
}
// Traverse the string from end
// and repeat the same process
for (int i = sequence.size() - 1;
i >= 0; i--) {
if (sequence[i] == '(') {
// If there are no closing
// brackets to match it
if (stack2_.empty()) {
return false;
}
// Otherwise, pop character
// from stack
else {
stack2_.pop();
}
}
else {
stack2_.push(sequence[i]);
}
}
// Store the extra ( or ) which
// are not balanced yet
int extra = abs(countClosed - countOpen);
// Check if $ is available to
// balance the extra brackets
if (countSymbol < extra) {
return false;
}
else {
// Count ramaining $ after
// balancing extra ( and )
countSymbol -= extra;
// Check if each pair of $
// is convertible in ()
if (countSymbol % 2 == 0) {
return true;
}
}
return false;
}
// Driver Code
int main()
{
string S = "()($";
// Function Call
if (canBeBalanced(S)) {
cout << "Yes";
}
else {
cout << "No";
}
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to check if the String
// can be balanced by replacing the
// '$' with opening or closing brackets
static boolean canBeBalanced(String sequence)
{
// If String can never be balanced
if (sequence.length() % 2 == 1)
return false;
// Declare 2 stacks to check if all
// ) can be balanced with ( or $
// and vice-versa
Stack<Character> stack_ = new Stack<Character>();
Stack<Character> stack2_ = new Stack<Character>();
// Store the count the occurrence
// of (, ) and $
int countOpen = 0, countClosed = 0;
int countSymbol = 0;
// Traverse the String
for (int i = 0;
i < sequence.length(); i++)
{
if (sequence.charAt(i) == ')')
{
// Increment closed bracket
// count by 1
countClosed++;
// If there are no opening
// bracket to match it
// then return false
if (stack_.isEmpty())
{
return false;
}
// Otherwise, pop the character
// from the stack
else
{
stack_.pop();
}
}
else
{
// If current character is
// an opening bracket or $,
// push it to the stack
if (sequence.charAt(i) == '$')
{
// Increment symbol
// count by 1
countSymbol++;
}
else
{
// Increment open
// bracket count by 1
countOpen++;
}
stack_.add(sequence.charAt(i));
}
}
// Traverse the String from end
// and repeat the same process
for (int i = sequence.length() - 1;
i >= 0; i--)
{
if (sequence.charAt(i) == '(')
{
// If there are no closing
// brackets to match it
if (stack2_.isEmpty())
{
return false;
}
// Otherwise, pop character
// from stack
else
{
stack2_.pop();
}
}
else
{
stack2_.add(sequence.charAt(i));
}
}
// Store the extra ( or ) which
// are not balanced yet
int extra = Math.abs(countClosed - countOpen);
// Check if $ is available to
// balance the extra brackets
if (countSymbol < extra)
{
return false;
}
else
{
// Count ramaining $ after
// balancing extra ( and )
countSymbol -= extra;
// Check if each pair of $
// is convertible in ()
if (countSymbol % 2 == 0)
{
return true;
}
}
return false;
}
// Driver Code
public static void main(String[] args)
{
String S = "()($";
// Function Call
if (canBeBalanced(S))
{
System.out.print("Yes");
}
else
{
System.out.print("No");
}
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach
# Function to check if the
# can be balanced by replacing the
# '$' with opening or closing brackets
def canBeBalanced(sequence):
# If string can never be balanced
if (len(sequence) % 2):
return False
# Declare 2 stacks to check if all
# ) can be balanced with ( or $
# and vice-versa
stack_, stack2_ = [], []
# Store the count the occurrence
# of (, ) and $
countOpen ,countClosed = 0, 0
countSymbol = 0
# Traverse the string
for i in range(len(sequence)):
if (sequence[i] == ')'):
# Increment closed bracket
# count by 1
countClosed += 1
# If there are no opening
# bracket to match it
# then return False
if (len(stack_) == 0):
return False
# Otherwise, pop the character
# from the stack
else:
del stack_[-1]
else:
# If current character is
# an opening bracket or $,
# push it to the stack
if (sequence[i] == '$'):
# Increment symbol
# count by 1
countSymbol += 1
else:
# Increment open
# bracket count by 1
countOpen += 1
stack_.append(sequence[i])
# Traverse the string from end
# and repeat the same process
for i in range(len(sequence)-1, -1, -1):
if (sequence[i] == '('):
# If there are no closing
# brackets to match it
if (len(stack2_) == 0):
return False
# Otherwise, pop character
# from stack
else:
del stack2_[-1]
else :
stack2_.append(sequence[i])
# Store the extra ( or ) which
# are not balanced yet
extra = abs(countClosed - countOpen)
# Check if $ is available to
# balance the extra brackets
if (countSymbol < extra):
return False
else :
# Count ramaining $ after
# balancing extra ( and )
countSymbol -= extra
# Check if each pair of $
# is convertible in ()
if (countSymbol % 2 == 0) :
return True
return False
# Driver Code
if __name__ == '__main__':
S = "()($"
# Function Call
if (canBeBalanced(S)):
print("Yes")
else:
print("No")
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to check if the String
// can be balanced by replacing the
// '$' with opening or closing brackets
static bool canBeBalanced(String sequence)
{
// If String can never be balanced
if (sequence.Length % 2 == 1)
return false;
// Declare 2 stacks to check if all
// ) can be balanced with ( or $
// and vice-versa
Stack<char> stack_ = new Stack<char>();
Stack<char> stack2_ = new Stack<char>();
// Store the count the occurrence
// of (, ) and $
int countOpen = 0, countClosed = 0;
int countSymbol = 0;
// Traverse the String
for (int i = 0;
i < sequence.Length; i++)
{
if (sequence[i] == ')')
{
// Increment closed bracket
// count by 1
countClosed++;
// If there are no opening
// bracket to match it
// then return false
if (stack_.Count==0)
{
return false;
}
// Otherwise, pop the character
// from the stack
else
{
stack_.Pop();
}
}
else
{
// If current character is
// an opening bracket or $,
// push it to the stack
if (sequence[i] == '$')
{
// Increment symbol
// count by 1
countSymbol++;
}
else
{
// Increment open
// bracket count by 1
countOpen++;
}
stack_.Push(sequence[i]);
}
}
// Traverse the String from end
// and repeat the same process
for (int i = sequence.Length - 1;
i >= 0; i--)
{
if (sequence[i] == '(')
{
// If there are no closing
// brackets to match it
if (stack2_.Count == 0)
{
return false;
}
// Otherwise, pop character
// from stack
else
{
stack2_.Pop();
}
}
else
{
stack2_.Push(sequence[i]);
}
}
// Store the extra ( or ) which
// are not balanced yet
int extra = Math.Abs(countClosed - countOpen);
// Check if $ is available to
// balance the extra brackets
if (countSymbol < extra)
{
return false;
}
else
{
// Count ramaining $ after
// balancing extra ( and )
countSymbol -= extra;
// Check if each pair of $
// is convertible in ()
if (countSymbol % 2 == 0)
{
return true;
}
}
return false;
}
// Driver Code
public static void Main(String[] args)
{
String S = "()($";
// Function Call
if (canBeBalanced(S))
{
Console.Write("Yes");
}
else
{
Console.Write("No");
}
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Function to check if the String
// can be balanced by replacing the
// '$' with opening or closing brackets
function canBeBalanced(sequence)
{
// If String can never be balanced
if (sequence.length % 2 == 1)
return false;
// Declare 2 stacks to check if all
// ) can be balanced with ( or $
// and vice-versa
let stack_ = [];
let stack2_ = [];
// Store the count the occurrence
// of (, ) and $
let countOpen = 0, countClosed = 0;
let countSymbol = 0;
// Traverse the String
for (let i = 0;
i < sequence.length; i++)
{
if (sequence[i] == ')')
{
// Increment closed bracket
// count by 1
countClosed++;
// If there are no opening
// bracket to match it
// then return false
if (stack_.length==0)
{
return false;
}
// Otherwise, pop the character
// from the stack
else
{
stack_.pop();
}
}
else
{
// If current character is
// an opening bracket or $,
// push it to the stack
if (sequence[i] == '$')
{
// Increment symbol
// count by 1
countSymbol++;
}
else
{
// Increment open
// bracket count by 1
countOpen++;
}
stack_.push(sequence[i]);
}
}
// Traverse the String from end
// and repeat the same process
for (let i = sequence.length - 1;
i >= 0; i--)
{
if (sequence[i] == '(')
{
// If there are no closing
// brackets to match it
if (stack2_.length==0)
{
return false;
}
// Otherwise, pop character
// from stack
else
{
stack2_.pop();
}
}
else
{
stack2_.push(sequence[i]);
}
}
// Store the extra ( or ) which
// are not balanced yet
let extra = Math.abs(countClosed - countOpen);
// Check if $ is available to
// balance the extra brackets
if (countSymbol < extra)
{
return false;
}
else
{
// Count ramaining $ after
// balancing extra ( and )
countSymbol -= extra;
// Check if each pair of $
// is convertible in ()
if (countSymbol % 2 == 0)
{
return true;
}
}
return false;
}
// Driver Code
let S = "()($";
// Function Call
if (canBeBalanced(S))
{
document.write("Yes");
}
else
{
document.write("No");
}
// This code is contributed by patel2127
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por se_prashant y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA