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.

  • 1
    $\begingroup$ Hint: make a case distinction on where to put the left-most opening parenthesis and its matching partner. $\endgroup$
    – Raphael
    Nov 24, 2015 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$ Nov 24, 2015 at 9:13

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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