snippetMinor
How to show all possible implied parenthesis?
Viewed 0 times
showallparenthesispossibleimpliedhow
Problem
Can I use recursion to find out the possible parenthesis we can add to this expression: 23-45 ?
(2(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)5) = 10
I am not able to find out the right states for the recursion to proceed. As at any point we wouldn't know if it would have two open parenthesis or two closed parenthesis. I am just looking for ideas.
(2(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)5) = 10
I am not able to find out the right states for the recursion to proceed. As at any point we wouldn't know if it would have two open parenthesis or two closed parenthesis. I am just looking for ideas.
Solution
I'm assuming the input expression does not contain parentheses.
The idea is that for each binary operator we pick it as the principle operator (which is at the root of the parse tree) and split the expression into two subexpressions.
Then we solve the subproblems recursively.
After that we combine those solutions prepending and appending parens and inserting the principle operator in the middle. Notice that there could be multiple solutions for both subproblems.
Also you need to figure out the base case for recursion.
The idea is that for each binary operator we pick it as the principle operator (which is at the root of the parse tree) and split the expression into two subexpressions.
Then we solve the subproblems recursively.
After that we combine those solutions prepending and appending parens and inserting the principle operator in the middle. Notice that there could be multiple solutions for both subproblems.
Also you need to figure out the base case for recursion.
Context
StackExchange Computer Science Q#49915, answer score: 3
Revisions (0)
No revisions yet.