Dada una string que contiene solo lo siguiente => ‘{‘, ‘}’, ‘(‘, ‘)’, ‘[‘, ‘]’. En algunos lugares hay una ‘X’ en lugar de cualquier paréntesis. Determine si reemplazando todas las ‘X’ con corchetes apropiados, es posible hacer una secuencia de corchetes válida.
Requisito previo: expresión de paréntesis equilibrada
Ejemplos:
Input : S = "{(X[X])}"
Output : Balanced
The balanced expression after
replacing X with suitable bracket is:
{([[]])}.
Input : [{X}(X)]
Output : Not balanced
No substitution of X with any bracket
results in a balanced expression.
Enfoque: Hemos discutido una solución para verificar si la expresión dada entre paréntesis está balanceada o no .
Siguiendo el mismo enfoque descrito en el artículo, se utiliza una estructura de datos de pila para verificar si la expresión dada está equilibrada o no. Para cada tipo de carácter en string, las operaciones a realizar en la pila son:
- ‘{‘ o ‘(‘ o ‘[‘ : cuando el elemento actual de la string es un corchete de apertura, empuja el elemento en la pila.
- ‘}’ o ‘]’ o ‘)’: cuando el elemento actual de la string es un corchete de cierre, extraiga el elemento superior de la pila y verifique si es un corchete de apertura que coincide con el corchete de cierre o no. Si coincide, pase al siguiente elemento de la string. Si no es así, entonces la string actual no está balanceada. También es posible que el elemento extraído de la pila sea ‘X’. En ese caso, ‘X’ es un paréntesis de apertura coincidente porque se empuja en la pila solo cuando se supone que es un paréntesis de apertura, como se describe en el siguiente paso.
- ‘X’: cuando el elemento actual es X, puede ser un corchete de inicio o un corchete de cierre. Primero suponga que se trata de un paréntesis inicial y llame recursivamente al siguiente elemento presionando X en la pila. Si el resultado de la recursión es falso, entonces X es un corchete de cierre que coincide con el corchete en la parte superior de la pila (si la pila no está vacía). Entonces, haga estallar el elemento superior y llame recursivamente al siguiente elemento. Si el resultado de la recursión es nuevamente falso, entonces la expresión no está balanceada.
También verifique el caso cuando la pila está vacía y el elemento actual es un corchete de cierre. En ese caso, la expresión no está balanceada.
Implementación:
C++
// C++ program to determine whether given
// expression is balanced/ parenthesis
// expression or not.
#include <bits/stdc++.h>
using namespace std;
// Function to check if two brackets are matching
// or not.
int isMatching(char a, char b)
{
if ((a == '{' && b == '}') || (a == '[' && b == ']')
|| (a == '(' && b == ')') || a == 'X')
return 1;
return 0;
}
// Recursive function to check if given expression
// is balanced or not.
int isBalanced(string s, stack<char> ele, int ind)
{
// Base case.
// If the string is balanced then all the opening
// brackets had been popped and stack should be
// empty after string is traversed completely.
if (ind == s.length())
return ele.empty();
// variable to store element at the top of the stack.
char topEle;
// variable to store result of recursive call.
int res;
// Case 1: When current element is an opening bracket
// then push that element in the stack.
if (s[ind] == '{' || s[ind] == '(' || s[ind] == '[') {
ele.push(s[ind]);
return isBalanced(s, ele, ind + 1);
}
// Case 2: When current element is a closing bracket
// then check for matching bracket at the top of the
// stack.
else if (s[ind] == '}' || s[ind] == ')' || s[ind] == ']') {
// If stack is empty then there is no matching opening
// bracket for current closing bracket and the
// expression is not balanced.
if (ele.empty())
return 0;
topEle = ele.top();
ele.pop();
// Check bracket is matching or not.
if (!isMatching(topEle, s[ind]))
return 0;
return isBalanced(s, ele, ind + 1);
}
// Case 3: If current element is 'X' then check
// for both the cases when 'X' could be opening
// or closing bracket.
else if (s[ind] == 'X') {
stack<char> tmp = ele;
tmp.push(s[ind]);
res = isBalanced(s, tmp, ind + 1);
if (res)
return 1;
if (ele.empty())
return 0;
ele.pop();
return isBalanced(s, ele, ind + 1);
}
}
int main()
{
string s = "{(X}[]";
stack<char> ele;
//Check if the String is of even length
if(s.length()%2==0){
if (isBalanced(s, ele, 0))
cout << "Balanced";
else
cout << "Not Balanced";
}
// If the length of the string is not even
// then it is not a balanced string
else{
cout << "Not Balanced";
}
return 0;
}
Java
// Java program to determine
// whether given expression
// is balanced/ parenthesis
// expression or not.
import java.util.Stack;
class GFG {
// Function to check if two
// brackets are matching or not.
static int isMatching(char a,
char b) {
if ((a == '{' && b == '}')
|| (a == '[' && b == ']')
|| (a == '(' && b == ')') || a == 'X') {
return 1;
}
return 0;
}
// Recursive function to
// check if given expression
// is balanced or not.
static int isBalanced(String s,
Stack<Character> ele,
int ind) {
// Base case.
// If the string is balanced
// then all the opening brackets
// had been popped and stack
// should be empty after string
// is traversed completely.
if (ind == s.length()) {
if (ele.size() == 0) {
return 1;
} else {
return 0;
}
}
// variable to store element
// at the top of the stack.
char topEle;
// variable to store result
// of recursive call.
int res;
// Case 1: When current element
// is an opening bracket
// then push that element
// in the stack.
if (s.charAt(ind) == '{'
|| s.charAt(ind) == '('
|| s.charAt(ind) == '[') {
ele.push(s.charAt(ind));
return isBalanced(s, ele, ind + 1);
} // Case 2: When current element
// is a closing bracket then
// check for matching bracket
// at the top of the stack.
else if (s.charAt(ind) == '}'
|| s.charAt(ind) == ')'
|| s.charAt(ind) == ']') {
// If stack is empty then there
// is no matching opening bracket
// for current closing bracket and
// the expression is not balanced.
if (ele.size() == 0) {
return 0;
}
topEle = ele.peek();
ele.pop();
// Check bracket is
// matching or not.
if (isMatching(topEle, s.charAt(ind)) == 0) {
return 0;
}
return isBalanced(s, ele, ind + 1);
} // Case 3: If current element
// is 'X' then check for both
// the cases when 'X' could be
// opening or closing bracket.
else if (s.charAt(ind) == 'X') {
Stack<Character> tmp = new Stack<>();
//because in java, direct assignment copies only reference and not the whole object
tmp.addAll(ele);
tmp.push(s.charAt(ind));
res = isBalanced(s, tmp, ind + 1);
if (res == 1) {
return 1;
}
if (ele.size() == 0) {
return 0;
}
ele.pop();
return isBalanced(s, ele, ind + 1);
}
return 1;
}
// Driver Code
public static void main(String[] args) {
String s = "{(X}[]";
Stack<Character> ele = new Stack<Character>();
// Check if the given string is of even length
if(s.length()%2==0){
if (isBalanced(s, ele, 0) != 0) {
System.out.println("Balanced");
} else {
System.out.println("Not Balanced");
}
}
// If the length of the string is not even
// then it is not a balanced string
else{
System.out.println("Not Balanced");
}
}
}
Python3
# Python3 program to determine whether
# given expression is balanced/ parenthesis
# expression or not.
# Function to check if two brackets are
# matching or not.
def isMatching(a, b):
if ((a == '{' and b == '}') or
(a == '[' and b == ']') or
(a == '(' and b == ')') or
a == 'X'):
return 1
return 0
# Recursive function to check if given
# expression is balanced or not.
def isBalanced(s, ele, ind):
# Base case.
# If the string is balanced then all the
# opening brackets had been popped and
# stack should be empty after string is
# traversed completely.
if (ind == len(s)):
if len(ele) == 0:
return True
else:
return False
# Variable to store element at the top
# of the stack.
# char topEle;
# Variable to store result of
# recursive call.
# int res;
# Case 1: When current element is an
# opening bracket then push that
# element in the stack.
if (s[ind] == '{' or s[ind] == '(' or
s[ind] == '['):
ele.append(s[ind])
return isBalanced(s, ele, ind + 1)
# Case 2: When current element is a closing
# bracket then check for matching bracket
# at the top of the stack.
elif (s[ind] == '}' or s[ind] == ')' or
s[ind] == ']'):
# If stack is empty then there is no matching
# opening bracket for current closing bracket
# and the expression is not balanced.
if (len(ele) == 0):
return 0
topEle = ele[-1]
ele.pop()
# Check bracket is matching or not.
if (isMatching(topEle, s[ind]) == 0):
return 0
return isBalanced(s, ele, ind + 1)
# Case 3: If current element is 'X' then check
# for both the cases when 'X' could be opening
# or closing bracket.
elif (s[ind] == 'X'):
tmp = ele
tmp.append(s[ind])
res = isBalanced(s, tmp, ind + 1)
if (res):
return 1
if (len(ele) == 0):
return 0
ele.pop()
return isBalanced(s, ele, ind + 1)
# Driver Code
s = "{(X}[]"
ele = []
# Check if the length of the given string is even
if(len(s)%2==0):
if (isBalanced(s, ele, 0)): print("Balanced")
else: print("Not Balanced")
# If the length is not even, then the string is not balanced
else: print("Not Balanced")
# This code is contributed by divyeshrabadiya07
C#
// C# program to determine
// whether given expression
// is balanced/ parenthesis
// expression or not.
using System;
using System.Collections.Generic;
class GFG
{
// Function to check if two
// brackets are matching or not.
static int isMatching(char a,
char b)
{
if ((a == '{' && b == '}') ||
(a == '[' && b == ']') ||
(a == '(' && b == ')') || a == 'X')
return 1;
return 0;
}
// Recursive function to
// check if given expression
// is balanced or not.
static int isBalanced(string s,
Stack<char> ele,
int ind)
{
// Base case.
// If the string is balanced
// then all the opening brackets
// had been popped and stack
// should be empty after string
// is traversed completely.
if (ind == s.Length)
{
if (ele.Count == 0)
return 1;
else
return 0;
}
// variable to store element
// at the top of the stack.
char topEle;
// variable to store result
// of recursive call.
int res;
// Case 1: When current element
// is an opening bracket
// then push that element
// in the stack.
if (s[ind] == '{' ||
s[ind] == '(' ||
s[ind] == '[')
{
ele.Push(s[ind]);
return isBalanced(s, ele, ind + 1);
}
// Case 2: When current element
// is a closing bracket then
// check for matching bracket
// at the top of the stack.
else if (s[ind] == '}' ||
s[ind] == ')' ||
s[ind] == ']')
{
// If stack is empty then there
// is no matching opening bracket
// for current closing bracket and
// the expression is not balanced.
if (ele.Count == 0)
return 0;
topEle = ele.Peek();
ele.Pop();
// Check bracket is
// matching or not.
if (isMatching(topEle, s[ind]) == 0)
return 0;
return isBalanced(s, ele, ind + 1);
}
// Case 3: If current element
// is 'X' then check for both
// the cases when 'X' could be
// opening or closing bracket.
else if (s[ind] == 'X')
{
Stack<char> tmp = ele;
tmp.Push(s[ind]);
res = isBalanced(s, tmp, ind + 1);
if (res == 1)
return 1;
if (ele.Count == 0)
return 0;
ele.Pop();
return isBalanced(s, ele, ind + 1);
}
return 1;
}
// Driver Code
static void Main()
{
string s = "{(X}[]";
Stack<char> ele = new Stack<char>();
// Check if the String is of even length
if(s.Length%2==0){
if (isBalanced(s, ele, 0) != 0)
Console.Write("Balanced");
else
Console.Write("Not Balanced");
}
// If the length of the string is not even
// then it is not a balanced string
else{
Console.Write("Not Balanced");
}
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
Javascript
<script>
// JavaScript program to determine whether given
// expression is balanced/ parenthesis
// expression or not.
// Function to check if two brackets are matching
// or not.
function isMatching(a, b)
{
if ((a == '{' && b == '}') || (a == '[' && b == ']')
|| (a == '(' && b == ')') || a == 'X')
return 1;
return 0;
}
// Recursive function to check if given expression
// is balanced or not.
function isBalanced(s, ele, ind)
{
// Base case.
// If the string is balanced then all the opening
// brackets had been popped and stack should be
// empty after string is traversed completely.
if (ind == s.length)
return ele.length==0;
// variable to store element at the top of the stack.
var topEle;
// variable to store result of recursive call.
var res;
// Case 1: When current element is an opening bracket
// then push that element in the stack.
if (s[ind] == '{' || s[ind] == '(' || s[ind] == '[') {
ele.push(s[ind]);
return isBalanced(s, ele, ind + 1);
}
// Case 2: When current element is a closing bracket
// then check for matching bracket at the top of the
// stack.
else if (s[ind] == '}' || s[ind] == ')' || s[ind] == ']') {
// If stack is empty then there is no matching opening
// bracket for current closing bracket and the
// expression is not balanced.
if (ele.length==0)
return 0;
topEle = ele[ele.length-1];
ele.pop();
// Check bracket is matching or not.
if (!isMatching(topEle, s[ind]))
return 0;
return isBalanced(s, ele, ind + 1);
}
// Case 3: If current element is 'X' then check
// for both the cases when 'X' could be opening
// or closing bracket.
else if (s[ind] == 'X') {
var tmp = ele;
tmp.push(s[ind]);
res = isBalanced(s, tmp, ind + 1);
if (res)
return 1;
if (ele.length==0)
return 0;
ele.pop();
return isBalanced(s, ele, ind + 1);
}
}
var s = "{(X}[]";
var ele = [];
if (isBalanced(s, ele, 0))
document.write( "Balanced");
else
document.write( "Not Balanced");
</script>
Producción
Balanced
Complejidad de tiempo: O((2^n)*n)
Espacio auxiliar: O(N)