Check for balanced parentheses in an expression | O(1) space
Given a string of length n having parentheses in it, your task is to find whether given string has balanced parentheses or not. Please note there is constraint on space i.e. we are allowed to use only O(1) extra space.
Also See : Check for balanced parentheses
Examples:
Input : (())[] Output : Yes Input : ))(({}{ Output : No
If k = 1, then we will simply keep a count variable c = 0, whenever we encounter an opening parentheses we will increment c and whenever we encounter a closing parentheses we will reduce the count of c, At any stage we shouldn’t have c < 0 and at the end we must have c = 0 for string to be balanced.
Following is the idea of our algorithm for this problem. For any opening bracket say ‘[‘ we find its matching closing bracket ‘]’. Let’s say index of ‘[‘ was i and index of ‘]’ was j then following conditions must be true:
- i < j
- for all k such that i < k < j, for all the opening parentheses(index-k) it’s matching closing parentheses x must satisfy k < x < j and for all the closing parentheses(index-k) it’s matching opening parentheses x must satisfy i < x < k
Implementation:
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> |
Yes No
Complexity Analysis:
- Time Complexity: O(n3)
- Auxiliary Space: O(1)
Contact Us