Remove Invalid Parentheses | C / C ++ program to remove invalid parenthesis ; method checks if character is parenthesis ( openor closed ) ; method returns true if string contains valid parenthesis ; method to remove invalid parenthesis ; visit set to ignore already visited string ; queue to maintain BFS ; pushing given string as starting node into queue ; If answer is found , make level true so that valid string of only that level are processed . ; Removing parenthesis from str and pushing into queue , if not visited already ; Driver code to check above methods
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isParenthesis ( char c ) { return ( ( c == ' ( ' ) || ( c == ' ) ' ) ) ; } bool isValidString ( string str ) { int cnt = 0 ; for ( int i = 0 ; i < str . length ( ) ; i ++ ) { if ( str [ i ] == ' ( ' ) cnt ++ ; else if ( str [ i ] == ' ) ' ) cnt -- ; if ( cnt < 0 ) return false ; } return ( cnt == 0 ) ; } void removeInvalidParenthesis ( string str ) { if ( str . empty ( ) ) return ; set < string > visit ; queue < string > q ; string temp ; bool level ; q . push ( str ) ; visit . insert ( str ) ; while ( ! q . empty ( ) ) { str = q . front ( ) ; q . pop ( ) ; if ( isValidString ( str ) ) { cout << str << endl ; level = true ; } if ( level ) continue ; for ( int i = 0 ; i < str . length ( ) ; i ++ ) { if ( ! isParenthesis ( str [ i ] ) ) continue ; temp = str . substr ( 0 , i ) + str . substr ( i + 1 ) ; if ( visit . find ( temp ) == visit . end ( ) ) { q . push ( temp ) ; visit . insert ( temp ) ; } } } } int main ( ) { string expression = " ( ) ( ) ) ( ) " ; removeInvalidParenthesis ( expression ) ; expression = " ( ) v ) " ; removeInvalidParenthesis ( expression ) ; return 0 ; }