Dadas dos secuencias de paréntesis S1 y S2 que consisten en ‘(‘ y ‘)’. La tarea es verificar si la string obtenida al concatenar ambas secuencias está balanceada o no. La concatenación se puede realizar mediante s1+s2 o s2+s1.
Ejemplos:
Entrada: s1 = “)()(())))”, s2 = “(()(()(”
Salida: Balanceada
s2 + s1 = “(()(()()()(())) )”, que
es una secuencia de paréntesis balanceada.Entrada: s1 = “(()))(“, s2 = “())())”
Salida: No balanceado
s1 + s2 = “(()))(())())” –> No balanceado
s2 + s1 = “())())(()))(” –> No balanceado
Una solución ingenua es primero concatenar ambas secuencias y luego verificar si la secuencia resultante está balanceada o no usando una pila. Primero, verifique si s1 + s2 está balanceado o no. De lo contrario, compruebe si s2 + s1 está equilibrado o no. Para verificar si una secuencia dada de paréntesis está balanceada o no usando una pila, se puede usar el siguiente algoritmo.
- Declara una pila de caracteres S.
- Ahora recorra la string de expresión exp.
- Si el carácter actual es un corchete de inicio (‘(‘ o ‘{‘ o ‘[‘) entonces empújelo para apilar.
- Si el carácter actual es un corchete de cierre (‘)’ o ‘}’ o ‘]’), entonces sáquelo de la pila y si el carácter reventado es el corchete de inicio coincidente, entonces bien, de lo contrario, los paréntesis no están equilibrados.
- Después de completar el recorrido, si queda algún paréntesis inicial en la pila, entonces «no está equilibrado».
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to check if sequence obtained
// by concatenating two bracket sequences
// is balanced or not.
#include <bits/stdc++.h>
using namespace std;
// Check if given string is balanced bracket
// sequence or not.
bool isBalanced(string s)
{
stack<char> st;
int n = s.length();
for (int i = 0; i < n; i++) {
// If current bracket is an opening
// bracket push it to stack.
if (s[i] == '(')
st.push(s[i]);
// If current bracket is a closing
// bracket then pop from stack if
// it is not empty. If stack is empty
// then sequence is not balanced.
else {
if (st.empty()) {
return false;
}
else
st.pop();
}
}
// If stack is not empty, then sequence
// is not balanced.
if (!st.empty())
return false;
return true;
}
// Function to check if string obtained by
// concatenating two bracket sequences is
// balanced or not.
bool isBalancedSeq(string s1, string s2)
{
// Check if s1 + s2 is balanced or not.
if (isBalanced(s1 + s2))
return true;
// Check if s2 + s1 is balanced or not.
return isBalanced(s2 + s1);
}
// Driver code.
int main()
{
string s1 = ")()(())))";
string s2 = "(()(()(";
if (isBalancedSeq(s1, s2))
cout << "Balanced";
else
cout << "Not Balanced";
return 0;
}
Java
// Java program to check if sequence obtained
// by concatenating two bracket sequences
// is balanced or not.
import java.util.Stack;
class GFG
{
// Check if given string is balanced bracket
// sequence or not.
static boolean isBalanced(String s)
{
Stack<Character> st = new Stack<Character>();
int n = s.length();
for (int i = 0; i < n; i++)
{
// If current bracket is an opening
// bracket push it to stack.
if (s.charAt(i) == '(')
{
st.push(s.charAt(i));
}
// If current bracket is a closing
// bracket then pop from stack if
// it is not empty. If stack is empty
// then sequence is not balanced.
else if (st.empty())
{
return false;
}
else
{
st.pop();
}
}
// If stack is not empty, then sequence
// is not balanced.
if (!st.empty())
{
return false;
}
return true;
}
// Function to check if string obtained by
// concatenating two bracket sequences is
// balanced or not.
static boolean isBalancedSeq(String s1, String s2)
{
// Check if s1 + s2 is balanced or not.
if (isBalanced(s1 + s2))
{
return true;
}
// Check if s2 + s1 is balanced or not.
return isBalanced(s2 + s1);
}
// Driver code.
public static void main(String[] args)
{
String s1 = ")()(())))";
String s2 = "(()(()(";
if (isBalancedSeq(s1, s2))
{
System.out.println("Balanced");
}
else
{
System.out.println("Not Balanced");
}
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to check if sequence obtained
# by concatenating two bracket sequences
# is balanced or not.
# Check if given string is balanced bracket
# sequence or not.
def isBalanced(s):
st = list()
n = len(s)
for i in range(n):
# If current bracket is an opening
# bracket push it to stack.
if s[i] == '(':
st.append(s[i])
# If current bracket is a closing
# bracket then pop from stack if
# it is not empty. If stack is empty
# then sequence is not balanced.
else:
if len(st) == 0:
return False
else:
st.pop()
# If stack is not empty, then sequence
# is not balanced.
if len(st) > 0:
return False
return True
# Function to check if string obtained by
# concatenating two bracket sequences is
# balanced or not.
def isBalancedSeq(s1, s2):
# Check if s1 + s2 is balanced or not.
if (isBalanced(s1 + s2)):
return True
# Check if s2 + s1 is balanced or not.
return isBalanced(s2 + s1)
# Driver Code
if __name__ == "__main__":
s1 = ")()(())))"
s2 = "(()(()("
if isBalancedSeq(s1, s2):
print("Balanced")
else:
print("Not Balanced")
# This code is contributed by
# sanjeev2552
C#
// C# program to check if sequence obtained
// by concatenating two bracket sequences
// is balanced or not.
using System;
using System.Collections.Generic;
class GFG
{
// Check if given string is balanced bracket
// sequence or not.
static bool isBalanced(String s)
{
Stack<char> st = new Stack<char>();
int n = s.Length;
for (int i = 0; i < n; i++)
{
// If current bracket is an opening
// bracket push it to stack.
if (s[i] == '(')
{
st.Push(s[i]);
}
// If current bracket is a closing
// bracket then pop from stack if
// it is not empty. If stack is empty
// then sequence is not balanced.
else if (st.Count==0)
{
return false;
}
else
{
st.Pop();
}
}
// If stack is not empty, then sequence
// is not balanced.
if (st.Count!=0)
{
return false;
}
return true;
}
// Function to check if string obtained by
// concatenating two bracket sequences is
// balanced or not.
static bool isBalancedSeq(String s1, String s2)
{
// Check if s1 + s2 is balanced or not.
if (isBalanced(s1 + s2))
{
return true;
}
// Check if s2 + s1 is balanced or not.
return isBalanced(s2 + s1);
}
// Driver code.
public static void Main(String[] args)
{
String s1 = ")()(())))";
String s2 = "(()(()(";
if (isBalancedSeq(s1, s2))
{
Console.WriteLine("Balanced");
}
else
{
Console.WriteLine("Not Balanced");
}
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// Javascript program to check if sequence
// obtained by concatenating two bracket
// sequences is balanced or not.
// Check if given string is balanced
// bracket sequence or not.
function isBalanced(s)
{
let st = [];
let n = s.length;
for(let i = 0; i < n; i++)
{
// If current bracket is an opening
// bracket push it to stack.
if (s[i] == '(')
{
st.push(s[i]);
}
// If current bracket is a closing
// bracket then pop from stack if
// it is not empty. If stack is empty
// then sequence is not balanced.
else if (st.length == 0)
{
return false;
}
else
{
st.pop();
}
}
// If stack is not empty, then sequence
// is not balanced.
if (st.length != 0)
{
return false;
}
return true;
}
// Function to check if string obtained by
// concatenating two bracket sequences is
// balanced or not.
function isBalancedSeq(s1, s2)
{
// Check if s1 + s2 is balanced or not.
if (isBalanced(s1 + s2))
{
return true;
}
// Check if s2 + s1 is balanced or not.
return isBalanced(s2 + s1);
}
// Driver code
let s1 = ")()(())))";
let s2 = "(()(()(";
if (isBalancedSeq(s1, s2))
{
document.write("Balanced");
}
else
{
document.write("Not Balanced");
}
// This code is contributed by mukesh07
</script>
Producción:
Balanced
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Una solución eficiente es verificar si las secuencias dadas pueden resultar en una secuencia de paréntesis balanceada sin usar una pila, es decir, en un espacio adicional constante.
Sea la sucesión concatenada s. Hay dos posibilidades: s = s1 + s2 está balanceado o s = s2 + s1 está balanceado. Verifique ambas posibilidades si s está balanceado o no.
- Si s está equilibrado, entonces el número de paréntesis de apertura en s siempre debe ser mayor o igual que el número de paréntesis de cierre en S en cualquier instante de su recorrido. Esto se debe a que si en cualquier instante el número de paréntesis de cierre en s es mayor que el número de paréntesis de apertura, entonces el último paréntesis de cierre no tendrá un paréntesis de apertura coincidente (por eso la cuenta es más) en s.
- Si la secuencia está equilibrada, al final del recorrido, el número de paréntesis de apertura en s es igual al número de paréntesis de cierre en s.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if sequence obtained
// by concatenating two bracket sequences
// is balanced or not.
#include <bits/stdc++.h>
using namespace std;
// Check if given string is balanced bracket
// sequence or not.
bool isBalanced(string s)
{
// To store result of comparison of
// count of opening brackets and
// closing brackets.
int cnt = 0;
int n = s.length();
for (int i = 0; i < n; i++) {
// If current bracket is an
// opening bracket, then
// increment count.
if (s[i] == '(')
cnt++;
// If current bracket is a
// closing bracket, then
// decrement count and check
// if count is negative.
else {
cnt--;
if (cnt < 0)
return false;
}
}
// If count is positive then
// some opening brackets are
// not balanced.
if (cnt > 0)
return false;
return true;
}
// Function to check if string obtained by
// concatenating two bracket sequences is
// balanced or not.
bool isBalancedSeq(string s1, string s2)
{
// Check if s1 + s2 is balanced or not.
if (isBalanced(s1 + s2))
return true;
// Check if s2 + s1 is balanced or not.
return isBalanced(s2 + s1);
}
// Driver code.
int main()
{
string s1 = ")()(())))";
string s2 = "(()(()(";
if (isBalancedSeq(s1, s2))
cout << "Balanced";
else
cout << "Not Balanced";
return 0;
}
Java
// Java program to check if
// sequence obtained by
// concatenating two bracket
// sequences is balanced or not.
import java.io.*;
class GFG
{
// Check if given string
// is balanced bracket
// sequence or not.
static boolean isBalanced(String s)
{
// To store result of comparison
// of count of opening brackets
// and closing brackets.
int cnt = 0;
int n = s.length();
for (int i = 0; i < n; i++)
{
// If current bracket is
// an opening bracket,
// then increment count.
if (s.charAt(i) =='(')
{
cnt = cnt + 1;
}
// If current bracket is a
// closing bracket, then
// decrement count and check
// if count is negative.
else
{
cnt = cnt - 1;
if (cnt < 0)
return false;
}
}
// If count is positive then
// some opening brackets are
// not balanced.
if (cnt > 0)
return false;
return true;
}
// Function to check if string
// obtained by concatenating
// two bracket sequences is
// balanced or not.
static boolean isBalancedSeq(String s1,
String s2)
{
// Check if s1 + s2 is
// balanced or not.
if (isBalanced(s1 + s2))
return true;
// Check if s2 + s1 is
// balanced or not.
return isBalanced(s2 + s1);
}
// Driver code
public static void main(String [] args)
{
String s1 = ")()(())))";
String s2 = "(()(()(";
if (isBalancedSeq(s1, s2))
{
System.out.println("Balanced");
}
else
{
System.out.println("Not Balanced");
}
}
}
// This code is contributed
// by Shivi_Aggarwal
Python3
# Python3 program to check
# if sequence obtained by
# concatenating two bracket
# sequences is balanced or not.
# Check if given string
# is balanced bracket
# sequence or not.
def isBalanced(s):
# To store result of
# comparison of count
# of opening brackets
# and closing brackets.
cnt = 0
n = len(s)
for i in range(0, n):
if (s[i] == '('):
cnt = cnt + 1
else :
cnt = cnt - 1
if (cnt < 0):
return False
if (cnt > 0):
return False
return True
def isBalancedSeq(s1, s2):
if (isBalanced(s1 + s2)):
return True
return isBalanced(s2 + s1)
# Driver code
a = ")()(())))";
b = "(()(()(";
if (isBalancedSeq(a, b)):
print("Balanced")
else:
print("Not Balanced")
# This code is contributed
# by Shivi_Aggarwal
C#
// C# program to check if
// sequence obtained by
// concatenating two bracket
// sequences is balanced or not.
using System;
class GFG
{
// Check if given string
// is balanced bracket
// sequence or not.
static bool isBalanced(String s)
{
// To store result of comparison
// of count of opening brackets
// and closing brackets.
int cnt = 0;
int n = s.Length;
for (int i = 0; i < n; i++)
{
// If current bracket is
// an opening bracket,
// then increment count.
if (s[i] =='(')
{
cnt = cnt + 1;
}
// If current bracket is a
// closing bracket, then
// decrement count and check
// if count is negative.
else
{
cnt = cnt - 1;
if (cnt < 0)
return false;
}
}
// If count is positive then
// some opening brackets are
// not balanced.
if (cnt > 0)
return false;
return true;
}
// Function to check if string
// obtained by concatenating
// two bracket sequences is
// balanced or not.
static bool isBalancedSeq(String s1,
String s2)
{
// Check if s1 + s2 is
// balanced or not.
if (isBalanced(s1 + s2))
return true;
// Check if s2 + s1 is
// balanced or not.
return isBalanced(s2 + s1);
}
// Driver code
public static void Main()
{
String s1 = ")()(())))";
String s2 = "(()(()(";
if (isBalancedSeq(s1, s2))
{
Console.WriteLine("Balanced");
}
else
{
Console.WriteLine("Not Balanced");
}
}
}
// This code is contributed by
// PrinciRaj1992
PHP
<?php
// PHP program to check if sequence obtained
// by concatenating two bracket sequences
// is balanced or not.
// Check if given string is balanced bracket
// sequence or not.
function isBalanced($s)
{
// To store result of comparison of
// count of opening brackets and
// closing brackets.
$cnt = 0;
$n = strlen($s);
for ($i = 0; $i < $n; $i++)
{
// If current bracket is an
// opening bracket, then
// increment count.
if ($s[$i] == '(')
$cnt++;
// If current bracket is a
// closing bracket, then
// decrement count and check
// if count is negative.
else
{
$cnt--;
if ($cnt < 0)
return false;
}
}
// If count is positive then
// some opening brackets are
// not balanced.
if ($cnt > 0)
return false;
return true;
}
// Function to check if string obtained by
// concatenating two bracket sequences is
// balanced or not.
function isBalancedSeq($s1, $s2)
{
// Check if s1 + s2 is balanced or not.
if (isBalanced($s1 + $s2))
return true;
// Check if s2 + s1 is balanced or not.
return isBalanced($s2 + $s1);
}
// Driver code.
$s1 = ")()(())))";
$s2 = "(()(()(";
if (!isBalancedSeq($s1, $s2))
echo "Balanced";
else
echo "Not Balanced";
// This code is contributed by ajit.
?>
Javascript
<script>
// Javascript program to check if sequence obtained
// by concatenating two bracket sequences
// is balanced or not.
// Check if given string is balanced bracket
// sequence or not.
function isBalanced(s)
{
// To store result of comparison of
// count of opening brackets and
// closing brackets.
var cnt = 0;
var n = s.length;
for (var i = 0; i < n; i++) {
// If current bracket is an
// opening bracket, then
// increment count.
if (s[i] == '(')
cnt++;
// If current bracket is a
// closing bracket, then
// decrement count and check
// if count is negative.
else {
cnt--;
if (cnt < 0)
return false;
}
}
// If count is positive then
// some opening brackets are
// not balanced.
if (cnt > 0)
return false;
return true;
}
// Function to check if string obtained by
// concatenating two bracket sequences is
// balanced or not.
function isBalancedSeq(s1, s2)
{
// Check if s1 + s2 is balanced or not.
if (isBalanced(s1 + s2))
return true;
// Check if s2 + s1 is balanced or not.
return isBalanced(s2 + s1);
}
// Driver code.
var s1 = ")()(())))";
var s2 = "(()(()(";
if (isBalancedSeq(s1, s2))
document.write( "Balanced");
else
document.write( "Not Balanced");
</script>
Producción:
Balanced
Complejidad temporal: O(n)
Espacio auxiliar: O(1)