Check for balanced parentheses in an expression | 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
< ? php 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 ; } 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 isBalanced ( $ X , $ n ) { $ 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 ; } $ X = str_split ( " [ ( ) ] ( ) " ) ; $ n = 6 ; if ( isBalanced ( $ X , $ n ) ) echo ( " Yes STRNEWLINE " ) ; else echo ( " No STRNEWLINE " ) ; $ Y = str_split ( " [ [ ( ) ] ] ) " ) ; $ n = 7 ; if ( isBalanced ( $ Y , $ n ) ) echo ( " Yes STRNEWLINE " ) ; else echo ( " No STRNEWLINE " ) ; ? >