Check for balanced parentheses in an expression | O ( 1 ) space | C ++ 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
#include <stdio.h> NEW_LINE #include <stdlib.h> NEW_LINE 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 ; } 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 ; } bool isBalanced ( char X [ ] , int n ) { int i , j , 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 ; } int main ( ) { char X [ ] = " [ ( ) ] ( ) " ; int n = 6 ; if ( isBalanced ( X , n ) ) printf ( " Yes STRNEWLINE " ) ; else printf ( " No STRNEWLINE " ) ; char Y [ ] = " [ [ ( ) ] ] ) " ; n = 7 ; if ( isBalanced ( Y , n ) ) printf ( " Yes STRNEWLINE " ) ; else printf ( " No STRNEWLINE " ) ; return 0 ; }