Dada una string de expresión exp, escriba un programa para examinar si los pares y los órdenes de “{“, ”}”, ”(“, )”, ”[“, ”]” son correctos en exp.
Ejemplos:
Input : exp = “[()]{}{[()()]()}”
Output : true
Input : exp = “[(])”
Output : false
Hemos discutido una solución basada en pila . Aquí no se nos permite usar la pila. Parece que este problema no se puede resolver sin espacio adicional (consulte los comentarios al final). Usamos la recursividad para resolver el problema.
A continuación se muestra la implementación del algoritmo anterior:
C++
// CPP program to check if parenthesis are
// balanced or not in an expression.
#include <bits/stdc++.h>
using namespace std;
char findClosing(char c)
{
if (c == '(')
return ')';
if (c == '{')
return '}';
if (c == '[')
return ']';
return -1;
}
// function to check if parenthesis are
// balanced.
bool check(char expr[], int n)
{
// Base cases
if (n == 0)
return true;
if (n == 1)
return false;
if (expr[0] == ')' || expr[0] == '}' || expr[0] == ']')
return false;
// Search for closing bracket for first
// opening bracket.
char closing = findClosing(expr[0]);
// count is used to handle cases like
// "((()))". We basically need to
// consider matching closing bracket.
int i, count = 0;
for (i = 1; i < n; i++) {
if (expr[i] == expr[0])
count++;
if (expr[i] == closing) {
if (count == 0)
break;
count--;
}
}
// If we did not find a closing
// bracket
if (i == n)
return false;
// If closing bracket was next
// to open
if (i == 1)
return check(expr + 2, n - 2);
// If closing bracket was somewhere
// in middle.
return check(expr + 1, i - 1) && check(expr + i + 1, n - i - 1);
}
// Driver program to test above function
int main()
{
char expr[] = "[(])";
int n = strlen(expr);
if (check(expr, n))
cout << "Balanced";
else
cout << "Not Balanced";
return 0;
}
Java
// Java program to check if parenthesis are
// balanced or not in an expression.
import java.util.Arrays;
class GFG {
static char findClosing(char c)
{
if (c == '(')
return ')';
if (c == '{')
return '}';
if (c == '[')
return ']';
return Character.MIN_VALUE;
}
// function to check if parenthesis are
// balanced.
static boolean check(char expr[], int n)
{
// Base cases
if (n == 0)
return true;
if (n == 1)
return false;
if (expr[0] == ')' || expr[0] == '}' || expr[0] == ']')
return false;
// Search for closing bracket for first
// opening bracket.
char closing = findClosing(expr[0]);
// count is used to handle cases like
// "((()))". We basically need to
// consider matching closing bracket.
int i, count = 0;
for (i = 1; i < n; i++) {
if (expr[i] == expr[0])
count++;
if (expr[i] == closing) {
if (count == 0)
break;
count--;
}
}
// If we did not find a closing
// bracket
if (i == n)
return false;
// If closing bracket was next
// to open
if (i == 1)
return check(Arrays.copyOfRange(expr, i + 1, n), n - 2);
// If closing bracket was somewhere
// in middle.
return check(Arrays.copyOfRange(expr, 1, n), i - 1) && check(Arrays.copyOfRange(expr, (i + 1), n), n - i - 1);
}
// Driver code
public static void main(String[] args)
{
char expr[] = "[(])".toCharArray();
int n = expr.length;
if (check(expr, n))
System.out.println("Balanced");
else
System.out.println("Not Balanced");
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python3 program to check if parenthesis are
# balanced or not in an expression.
def findClosing(c):
if c == '(':
return ')'
elif c == '{':
return '}'
elif c == '[':
return ']'
return -1
# function to check if parenthesis
# are balanced.
def check(expr, n):
# Base cases
if n == 0:
return True
if n == 1:
return False
if expr[0] == ')' or \
expr[0] == '}' or expr[0] == ']':
return False
# Search for closing bracket for first
# opening bracket.
closing = findClosing(expr[0])
# count is used to handle cases like
# "((()))". We basically need to
# consider matching closing bracket.
i = -1
count = 0
for i in range(1, n):
if expr[i] == expr[0]:
count += 1
if expr[i] == closing:
if count == 0:
break
count -= 1
# If we did not find a closing
# bracket
if i == n:
return False
# If closing bracket was next
# to open
if i == 1:
return check(expr[2:], n - 2)
# If closing bracket was somewhere
# in middle.
return check(expr[1:], i - 1) and \
check(expr[i + 1:], n - i - 1)
# Driver Code
if __name__ == "__main__":
expr = "[(])"
n = len(expr)
if check(expr, n):
print("Balanced")
else:
print("Not Balanced")
# This code is contributed by
# sanjeev2552
C#
// C# program to check
// if parenthesis are
// balanced or not in
// an expression.
using System;
class GFG{
static char[] copyOfRange (char[] src,
int start,
int end)
{
int len = end - start;
char[] dest = new char[len];
Array.Copy(src, start,
dest, 0, len);
return dest;
}
static char findClosing(char c)
{
if (c == '(')
return ')';
if (c == '{')
return '}';
if (c == '[')
return ']';
return char.MinValue;
}
// Function to check if
// parenthesis are balanced.
static bool check(char []expr,
int n)
{
// Base cases
if (n == 0)
return true;
if (n == 1)
return false;
if (expr[0] == ')' ||
expr[0] == '}' ||
expr[0] == ']')
return false;
// Search for closing bracket for first
// opening bracket.
char closing = findClosing(expr[0]);
// count is used to handle cases like
// "((()))". We basically need to
// consider matching closing bracket.
int i, count = 0;
for (i = 1; i < n; i++)
{
if (expr[i] == expr[0])
count++;
if (expr[i] == closing)
{
if (count == 0)
break;
count--;
}
}
// If we did not find
// a closing bracket
if (i == n)
return false;
// If closing bracket
// was next to open
if (i == 1)
return check(copyOfRange(expr,
i + 1, n),
n - 2);
// If closing bracket
// was somewhere in middle.
return check(copyOfRange(expr, 1, n),
i - 1) &&
check(copyOfRange(expr, (i + 1),
n), n - i - 1);
}
// Driver code
public static void Main(String[] args)
{
char []expr = "[(])".ToCharArray();
int n = expr.Length;
if (check(expr, n))
Console.WriteLine("Balanced");
else
Console.WriteLine("Not Balanced");
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program to check if parenthesis are
// balanced or not in an expression.
function findClosing(c)
{
if (c == '(')
return ')';
if (c == '{')
return '}';
if (c == '[')
return ']';
return -1;
}
// function to check if parenthesis are
// balanced.
function check(expr, n)
{
// Base cases
if (n == 0)
return true;
if (n == 1)
return false;
if (expr[0] == ')' || expr[0] == '}' || expr[0] == ']')
return false;
// Search for closing bracket for first
// opening bracket.
var closing = findClosing(expr[0]);
// count is used to handle cases like
// "((()))". We basically need to
// consider matching closing bracket.
var i, count = 0;
for (i = 1; i < n; i++) {
if (expr[i] == expr[0])
count++;
if (expr[i] == closing) {
if (count == 0)
break;
count--;
}
}
// If we did not find a closing
// bracket
if (i == n)
return false;
// If closing bracket was next
// to open
if (i == 1)
return check(expr + 2, n - 2);
// If closing bracket was somewhere
// in middle.
return check(expr + 1, i - 1) && check(expr + i + 1, n - i - 1);
}
// Driver program to test above function
var expr = "[(])";
var n = expr.length;
if (check(expr, n))
document.write( "Balanced");
else
document.write( "Not Balanced");
// This code is contributed by itsok.
</script>
Producción:
Not Balanced
La solución anterior es muy ineficiente en comparación con la solución basada en pilas. Esto parece útil solo para problemas de práctica de recursividad.