How to show all possible implied parenthesis?

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.

• Hint: make a case distinction on where to put the left-most opening parenthesis and its matching partner. – Raphael Nov 24 '15 at 8:36
• 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. – David Richerby Nov 24 '15 at 9:13