5
$\begingroup$

Can I use recursion to find out the possible parenthesis we can add to this expression: 2*3-4*5 ?

(2*(3-(4*5))) = -34

((2*3)-(4*5)) = -14

((2*(3-4))*5) = -10

(2*((3-4)*5)) = -10

(((2*3)-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.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Hint: make a case distinction on where to put the left-most opening parenthesis and its matching partner. $\endgroup$ – Raphael♦ Nov 24 '15 at 8:36
  • 2
    $\begingroup$ I don't understand your question. Recursion is just a programming technique so the answer to "Can I use recursion to do X" is almost always "Yes, as long as X is possible." I don't know what you mean by "states for the recursion to proceed" and your point about not knowing whether you'd have a specific number of open or closed parens at a particular point makes it look like you already have a partial solution in mind and you're asking for help completing it -- except we don't know what that partial solution is. $\endgroup$ – David Richerby Nov 24 '15 at 9:13
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.