Dada una string de longitud n que tiene paréntesis, su tarea es encontrar si la string dada tiene paréntesis equilibrados o no. Tenga en cuenta que existe una restricción de espacio, es decir, solo se nos permite usar O (1) espacio adicional.
Ver también: Comprobar paréntesis equilibrados
Ejemplos:
Input : (())[] Output : Yes Input : ))(({}{ Output : No
C++
// C++ code to check balanced parentheses with // O(1) space. #include <stdio.h> #include <stdlib.h> // Function1 to match closing bracket int matchClosing(char X[], int start, int end, char open, char close) { int c = 1; int i = start + 1; while (i <= end) { if (X[i] == open) c++; else if (X[i] == close) c--; if (c == 0) return i; i++; } return i; } // Function1 to match opening bracket int matchingOpening(char X[], int start, int end, char open, char close) { int c = -1; int i = end - 1; while (i >= start) { if (X[i] == open) c++; else if (X[i] == close) c--; if (c == 0) return i; i--; } return -1; } // Function to check balanced parentheses bool isBalanced(char X[], int n) { // helper variables int i, j, k, x, start, end; for (i = 0; i < n; i++) { // Handling case of opening parentheses if (X[i] == '(') j = matchClosing(X, i, n - 1, '(', ')'); else if (X[i] == '{') j = matchClosing(X, i, n - 1, '{', '}'); else if (X[i] == '[') j = matchClosing(X, i, n - 1, '[', ']'); // Handling case of closing parentheses else { if (X[i] == ')') j = matchingOpening(X, 0, i, '(', ')'); else if (X[i] == '}') j = matchingOpening(X, 0, i, '{', '}'); else if (X[i] == ']') j = matchingOpening(X, 0, i, '[', ']'); // If corresponding matching // opening parentheses doesn't // lie in given interval return 0 if (j < 0 || j >= i) return false; // else continue continue; } // If corresponding closing parentheses // doesn't lie in given interval // return 0 if (j >= n || j < 0) return false; // if found, now check for each // opening and closing parentheses // in this interval start = i; end = j; for (k = start + 1; k < end; k++) { if (X[k] == '(') { x = matchClosing(X, k, end, '(', ')'); if (!(k < x && x < end)) { return false; } } else if (X[k] == ')') { x = matchingOpening(X, start, k, '(', ')'); if (!(start < x && x < k)) { return false; } } if (X[k] == '{') { x = matchClosing(X, k, end, '{', '}'); if (!(k < x && x < end)) { return false; } } else if (X[k] == '}') { x = matchingOpening(X, start, k, '{', '}'); if (!(start < x && x < k)) { return false; } } if (X[k] == '[') { x = matchClosing(X, k, end, '[', ']'); if (!(k < x && x < end)) { return false; } } else if (X[k] == ']') { x = matchingOpening(X, start, k, '[', ']'); if (!(start < x && x < k)) { return false; } } } } return true; } // Driver Code int main() { char X[] = "[()]()"; int n = 6; if (isBalanced(X, n)) printf("Yes\n"); else printf("No\n"); char Y[] = "[[()]])"; n = 7; if (isBalanced(Y, n)) printf("Yes\n"); else printf("No\n"); return 0; }
Java
// Java code to check balanced parentheses with // O(1) space. class GFG { // Function1 to match closing bracket static int matchClosing(char X[], int start, int end, char open, char close) { int c = 1; int i = start + 1; while (i <= end) { if (X[i] == open) { c++; } else if (X[i] == close) { c--; } if (c == 0) { return i; } i++; } return i; } // Function1 to match opening bracket static int matchingOpening(char X[], int start, int end, char open, char close) { int c = -1; int i = end - 1; while (i >= start) { if (X[i] == open) { c++; } else if (X[i] == close) { c--; } if (c == 0) { return i; } i--; } return -1; } // Function to check balanced parentheses static boolean isBalanced(char X[], int n) { // helper variables int i, j = 0, k, x, start, end; for (i = 0; i < n; i++) { // Handling case of opening parentheses if (X[i] == '(') { j = matchClosing(X, i, n - 1, '(', ')'); } else if (X[i] == '{') { j = matchClosing(X, i, n - 1, '{', '}'); } else if (X[i] == '[') { j = matchClosing(X, i, n - 1, '[', ']'); } // Handling case of closing parentheses else { if (X[i] == ')') { j = matchingOpening(X, 0, i, '(', ')'); } else if (X[i] == '}') { j = matchingOpening(X, 0, i, '{', '}'); } else if (X[i] == ']') { j = matchingOpening(X, 0, i, '[', ']'); } // If corresponding matching // opening parentheses doesn't // lie in given interval return 0 if (j < 0 || j >= i) { return false; } // else continue continue; } // If corresponding closing parentheses // doesn't lie in given interval // return 0 if (j >= n || j < 0) { return false; } // if found, now check for each // opening and closing parentheses // in this interval start = i; end = j; for (k = start + 1; k < end; k++) { if (X[k] == '(') { x = matchClosing(X, k, end, '(', ')'); if (!(k < x && x < end)) { return false; } } else if (X[k] == ')') { x = matchingOpening(X, start, k, '(', ')'); if (!(start < x && x < k)) { return false; } } if (X[k] == '{') { x = matchClosing(X, k, end, '{', '}'); if (!(k < x && x < end)) { return false; } } else if (X[k] == '}') { x = matchingOpening(X, start, k, '{', '}'); if (!(start < x && x < k)) { return false; } } if (X[k] == '[') { x = matchClosing(X, k, end, '[', ']'); if (!(k < x && x < end)) { return false; } } else if (X[k] == ']') { x = matchingOpening(X, start, k, '[', ']'); if (!(start < x && x < k)) { return false; } } } } return true; } // Driver Code public static void main(String[] args) { char X[] = "[()]()".toCharArray(); int n = 6; if (isBalanced(X, n)) System.out.printf("Yes\n"); else System.out.printf("No\n"); char Y[] = "[[()]])".toCharArray(); n = 7; if (isBalanced(Y, n)) System.out.printf("Yes\n"); else System.out.printf("No\n"); } } //this code contributed by Rajput-Ji
Python 3
# Python 3 code to check balanced # parentheses with O(1) space. # Function1 to match closing bracket def matchClosing(X, start, end, open, close): c = 1 i = start + 1 while (i <= end): if (X[i] == open): c += 1 elif (X[i] == close): c -= 1 if (c == 0): return i i += 1 return i # Function1 to match opening bracket def matchingOpening(X, start, end, open, close): c = -1 i = end - 1 while (i >= start): if (X[i] == open): c += 1 elif (X[i] == close): c -= 1 if (c == 0): return i i -= 1 return -1 # Function to check balanced # parentheses def isBalanced(X, n): for i in range(n): # Handling case of opening # parentheses if (X[i] == '('): j = matchClosing(X, i, n - 1, '(', ')') elif (X[i] == '{'): j = matchClosing(X, i, n - 1, '{', '}') elif (X[i] == '['): j = matchClosing(X, i, n - 1, '[', ']') # Handling case of closing # parentheses else : if (X[i] == ')'): j = matchingOpening(X, 0, i, '(', ')') elif (X[i] == '}'): j = matchingOpening(X, 0, i, '{', '}') elif (X[i] == ']'): j = matchingOpening(X, 0, i, '[', ']') # If corresponding matching opening # parentheses doesn't lie in given # interval return 0 if (j < 0 or j >= i): return False # else continue continue # If corresponding closing parentheses # doesn't lie in given interval, return 0 if (j >= n or j < 0): return False # if found, now check for each opening and # closing parentheses in this interval start = i end = j for k in range(start + 1, end) : if (X[k] == '(') : x = matchClosing(X, k, end, '(', ')') if (not(k < x and x < end)): return False elif (X[k] == ')'): x = matchingOpening(X, start, k, '(', ')') if (not(start < x and x < k)): return False if (X[k] == '{'): x = matchClosing(X, k, end, '{', '}') if (not(k < x and x < end)): return False elif (X[k] == '}'): x = matchingOpening(X, start, k, '{', '}') if (not(start < x and x < k)): return False if (X[k] == '['): x = matchClosing(X, k, end, '[', ']') if (not(k < x and x < end)): return False elif (X[k] == ']'): x = matchingOpening(X, start, k, '[', ']') if (not(start < x and x < k)): return False return True # Driver Code if __name__ == "__main__": X = "[()]()" n = 6 if (isBalanced(X, n)): print("Yes") else: print("No") Y = "[[()]])" n = 7 if (isBalanced(Y, n)): print("Yes") else: print("No") # This code is contributed by ita_c
C#
// C# code to check balanced parentheses with // O(1) space. using System; public class GFG { // Function1 to match closing bracket static int matchClosing(char []X, int start, int end, char open, char close) { int c = 1; int i = start + 1; while (i <= end) { if (X[i] == open) { c++; } else if (X[i] == close) { c--; } if (c == 0) { return i; } i++; } return i; } // Function1 to match opening bracket static int matchingOpening(char []X, int start, int end, char open, char close) { int c = -1; int i = end - 1; while (i >= start) { if (X[i] == open) { c++; } else if (X[i] == close) { c--; } if (c == 0) { return i; } i--; } return -1; } // Function to check balanced parentheses static bool isBalanced(char []X, int n) { // helper variables int i, j = 0, k, x, start, end; for (i = 0; i < n; i++) { // Handling case of opening parentheses if (X[i] == '(') { j = matchClosing(X, i, n - 1, '(', ')'); } else if (X[i] == '{') { j = matchClosing(X, i, n - 1, '{', '}'); } else if (X[i] == '[') { j = matchClosing(X, i, n - 1, '[', ']'); } // Handling case of closing parentheses else { if (X[i] == ')') { j = matchingOpening(X, 0, i, '(', ')'); } else if (X[i] == '}') { j = matchingOpening(X, 0, i, '{', '}'); } else if (X[i] == ']') { j = matchingOpening(X, 0, i, '[', ']'); } // If corresponding matching // opening parentheses doesn't // lie in given interval return 0 if (j < 0 || j >= i) { return false; } // else continue continue; } // If corresponding closing parentheses // doesn't lie in given interval // return 0 if (j >= n || j < 0) { return false; } // if found, now check for each // opening and closing parentheses // in this interval start = i; end = j; for (k = start + 1; k < end; k++) { if (X[k] == '(') { x = matchClosing(X, k, end, '(', ')'); if (!(k < x && x < end)) { return false; } } else if (X[k] == ')') { x = matchingOpening(X, start, k, '(', ')'); if (!(start < x && x < k)) { return false; } } if (X[k] == '{') { x = matchClosing(X, k, end, '{', '}'); if (!(k < x && x < end)) { return false; } } else if (X[k] == '}') { x = matchingOpening(X, start, k, '{', '}'); if (!(start < x && x < k)) { return false; } } if (X[k] == '[') { x = matchClosing(X, k, end, '[', ']'); if (!(k < x && x < end)) { return false; } } else if (X[k] == ']') { x = matchingOpening(X, start, k, '[', ']'); if (!(start < x && x < k)) { return false; } } } } return true; } // Driver Code public static void Main() { char []X = "[()]()".ToCharArray(); int n = 6; if (isBalanced(X, n)) Console.Write("Yes\n"); else Console.Write("No\n"); char []Y = "[[()]])".ToCharArray(); n = 7; if (isBalanced(Y, n)) Console.Write("Yes\n"); else Console.Write("No\n"); } } // This code contributed by Rajput-Ji
PHP
<?php // PHP code to check balanced parentheses // with O(1) space. // Function1 to match closing bracket function matchClosing($X, $start, $end, $open, $close) { $c = 1; $i = $start + 1; while ($i <= $end) { if ($X[$i] == $open) { $c++; } else if ($X[$i] == $close) { $c--; } if ($c == 0) { return $i; } $i++; } return $i; } // Function1 to match opening bracket function matchingOpening($X, $start, $end, $open, $close) { $c = -1; $i = $end - 1; while ($i >= $start) { if ($X[$i] == $open) { $c++; } else if ($X[$i] == $close) { $c--; } if ($c == 0) { return $i; } $i--; } return -1; } // Function to check balanced parentheses function isBalanced($X, $n) { // helper variables $i; $j = 0; $k; $x; $start; $end; for ($i = 0; $i < $n; $i++) { // Handling case of opening parentheses if ($X[$i] == '(') { $j = matchClosing($X, $i, $n - 1, '(', ')'); } else if ($X[$i] == '{') { $j = matchClosing($X, $i, $n - 1, '{', '}'); } else if ($X[$i] == '[') { $j = matchClosing($X, $i, $n - 1, '[', ']'); } // Handling case of closing parentheses else { if ($X[$i] == ')') { $j = matchingOpening($X, 0, $i, '(', ')'); } else if ($X[$i] == '}') { $j = matchingOpening($X, 0, $i, '{', '}'); } else if ($X[$i] == ']') { $j = matchingOpening($X, 0, $i, '[', ']'); } // If corresponding matching opening parentheses // doesn't lie in given interval return 0 if ($j < 0 || $j >= $i) { return false; } // else continue continue; } // If corresponding closing parentheses // doesn't lie in given interval // return 0 if ($j >= $n || $j < 0) { return false; } // if found, now check for each opening // and closing parentheses in this interval $start = $i; $end = $j; for ($k = $start + 1; $k < $end; $k++) { if ($X[$k] == '(') { $x = matchClosing($X, $k, $end, '(', ')'); if (!($k < $x && $x < $end)) { return false; } } else if ($X[$k] == ')') { $x = matchingOpening($X, $start, $k, '(', ')'); if (!($start < $x && $x < $k)) { return false; } } if ($X[$k] == '{') { $x = matchClosing($X, $k, $end, '{', '}'); if (!($k < $x && $x < $end)) { return false; } } else if ($X[$k] == '}') { $x = matchingOpening($X, $start, $k, '{', '}'); if (!($start < $x && $x < $k)) { return false; } } if ($X[$k] == '[') { $x = matchClosing($X, $k, $end, '[', ']'); if (!($k < $x && $x < $end)) { return false; } } else if ($X[$k] == ']') { $x = matchingOpening($X, $start, $k, '[', ']'); if (!($start < $x && $x < $k)) { return false; } } } } return true; } // Driver Code $X = str_split("[()]()"); $n = 6; if (isBalanced($X, $n)) echo("Yes\n"); else echo("No\n"); $Y = str_split("[[()]])"); $n = 7; if (isBalanced($Y, $n)) echo("Yes\n"); else echo("No\n"); // This code contributed by Mukul Singh ?>
Javascript
<script> // Javascript code to check balanced parentheses with // O(1) space. // Function1 to match closing bracket function matchClosing(X,start,end,open,close) { let c = 1; let i = start + 1; while (i <= end) { if (X[i] == open) { c++; } else if (X[i] == close) { c--; } if (c == 0) { return i; } i++; } return i; } // Function1 to match opening bracket function matchingOpening(X,start,end,open,close) { let c = -1; let i = end - 1; while (i >= start) { if (X[i] == open) { c++; } else if (X[i] == close) { c--; } if (c == 0) { return i; } i--; } return -1; } // Function to check balanced parentheses function isBalanced(X,n) { // helper variables let i, j = 0, k, x, start, end; for (i = 0; i < n; i++) { // Handling case of opening parentheses if (X[i] == '(') { j = matchClosing(X, i, n - 1, '(', ')'); } else if (X[i] == '{') { j = matchClosing(X, i, n - 1, '{', '}'); } else if (X[i] == '[') { j = matchClosing(X, i, n - 1, '[', ']'); } // Handling case of closing parentheses else { if (X[i] == ')') { j = matchingOpening(X, 0, i, '(', ')'); } else if (X[i] == '}') { j = matchingOpening(X, 0, i, '{', '}'); } else if (X[i] == ']') { j = matchingOpening(X, 0, i, '[', ']'); } // If corresponding matching // opening parentheses doesn't // lie in given interval return 0 if (j < 0 || j >= i) { return false; } // else continue continue; } // If corresponding closing parentheses // doesn't lie in given interval // return 0 if (j >= n || j < 0) { return false; } // if found, now check for each // opening and closing parentheses // in this interval start = i; end = j; for (k = start + 1; k < end; k++) { if (X[k] == '(') { x = matchClosing(X, k, end, '(', ')'); if (!(k < x && x < end)) { return false; } } else if (X[k] == ')') { x = matchingOpening(X, start, k, '(', ')'); if (!(start < x && x < k)) { return false; } } if (X[k] == '{') { x = matchClosing(X, k, end, '{', '}'); if (!(k < x && x < end)) { return false; } } else if (X[k] == '}') { x = matchingOpening(X, start, k, '{', '}'); if (!(start < x && x < k)) { return false; } } if (X[k] == '[') { x = matchClosing(X, k, end, '[', ']'); if (!(k < x && x < end)) { return false; } } else if (X[k] == ']') { x = matchingOpening(X, start, k, '[', ']'); if (!(start < x && x < k)) { return false; } } } } return true; } // Driver Code let X="[()]()".split(""); let n = 6; if (isBalanced(X, n)) document.write("Yes<br>"); else document.write("No<br>"); let Y = "[[()]])".split(""); n = 7; if (isBalanced(Y, n)) document.write("Yes<br>"); else document.write("No<br>"); // This code is contributed by avanitrachhadiya2155 </script>
Publicación traducida automáticamente
Artículo escrito por UttamSaroha y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA