0 votes 0 votes A problem called Boolean Parenthesis Matching (match all parenthesis in an expression) can be solved by: Greedy Approach Recursion Dynamic Approach Both [B] and [C] Algorithms tbb-algorithms-2 + – Bikram asked May 26, 2017 • edited Aug 20, 2019 by Counsellor Bikram 499 views answer comment Share Follow See all 9 Comments See all 9 9 Comments reply shraddha priya commented May 31, 2017 reply Follow Share @bikram sir, But it can be done by recursion also,isn't it? So shouldn't both DP and Recursion be the answer? 0 votes 0 votes Bikram commented May 31, 2017 reply Follow Share Can you provide some document which support your views ? 0 votes 0 votes shraddha priya commented May 31, 2017 reply Follow Share Actually I had written a recursive code for the same a few days back. The code is as follows: # include<stdio.h> # define MAX_SIZE 100 void printParenthesis(int pos, int n, int open, int close) { static char str[MAX_SIZE]; if(close == n) { printf("%s \n", str); return; } else { if(open > close) { str[pos] = '}'; printParenthesis(pos+1, n, open, close+1); } if(open < n) { str[pos] = '{'; printParenthesis(pos+1, n, open+1, close); } } } int main() { int n; scanf("%d", &n); printParenthesis(0, n, 0, 0); getchar(); return 0; } 0 votes 0 votes shraddha priya commented May 31, 2017 reply Follow Share Oh sorry. This code is to generate all possible n pairs of balanced parentheses for a given value of n. I don't know if the problem given to us above can be solved by recursion or not. 0 votes 0 votes Bikram commented May 31, 2017 reply Follow Share so conclude your points ! 0 votes 0 votes shraddha priya commented May 31, 2017 reply Follow Share Well it must be dynamic programming then. 0 votes 0 votes Bikram commented May 31, 2017 reply Follow Share Be more specific , how you conclude to this statement ? and before that how you thought like that please elaborate .. it will help . 0 votes 0 votes shraddha priya commented May 31, 2017 reply Follow Share Sir, the code above generates all possible pairs of parenthesis. So if the parenthesis in the given expression match with one of the generated ones then we can conclude that we have balanced parenthesis , can't we? This way we have a recursive sol, isn't it? Alternatively, if we scan the expression and use a stack to push open parenthesis and pop it when a closed parenthesis comes, we can say we have balanced parenthesis. Please correct me if I'm wrong. 1 votes 1 votes Bikram commented Aug 30, 2017 reply Follow Share @ shraddha Yes , you are correct.. 0 votes 0 votes Please log in or register to add a comment.
Best answer 0 votes 0 votes it is a dynamic programming problem though we can use recursive approach .. so both option B and C are possible. Bikram answered May 26, 2017 • selected Aug 20, 2019 by Bikram Bikram comment Share Follow See 1 comment See all 1 1 comment reply Rishabh Gupta 2 commented Aug 30, 2017 reply Follow Share For creating a dynamic programming solution for any problem, we first create its recursive solution. So, it can also be solved recursively. It won't be efficient, but the question asks if it can be solved or not. 1 votes 1 votes Please log in or register to add a comment.