Check for balanced parentheses in an expression | O ( 1 ) space | Java code to check balanced parentheses with O ( 1 ) space . ; Function1 to match closing bracket ; Function1 to match opening bracket ; Function to check balanced parentheses ; helper variables ; Handling case of opening parentheses ; } Handling case of closing parentheses ; If corresponding matching opening parentheses doesn 't  lie in given interval return 0 ; else continue ; If corresponding closing parentheses doesn 't lie in given interval  return 0 ; if found , now check for each opening and closing parentheses in this interval ; Driver Code
class GFG { 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 ; } 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 ; } static boolean isBalanced ( char X [ ] , int n ) { int i , j = 0 , k , x , start , end ; for ( i = 0 ; i < n ; i ++ ) { 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 , ' [ ' , ' ] ' ) ; } 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 ( j < 0 j >= i ) { return false ; } continue ; } if ( j >= n j < 0 ) { return false ; } 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 ; } public static void main ( String [ ] args ) { char X [ ] = " [ ( ) ] ( ) " . toCharArray ( ) ; int n = 6 ; if ( isBalanced ( X , n ) ) System . out . printf ( "YesNEW_LINE"); else System . out . printf ( "NoNEW_LINE"); char Y [ ] = " [ [ ( ) ] ] ) " . toCharArray ( ) ; n = 7 ; if ( isBalanced ( Y , n ) ) System . out . printf ( "YesNEW_LINE"); else System . out . printf ( "NoNEW_LINE"); } }