((3-2)-1) = 0
(3-(2-1)) = 2
Input : expr = "5*4-3*2"
Output :
(5*(4-(3*2))) = -10
(5*((4-3)*2)) = 10
((5*4)-(3*2)) = 14
((5*(4-3))*2) = 10
(((5*4)-3)*2) = 34
We can solve this problem by parenthesizing all possible valid substring of the expression and then evaluating them, but as we can see that it will involve solving lots of repeating subproblem, to save ourselves we can follow a dynamic programming approach. We store the result for each substring in a map and if string in recursion is already solved, we return result from map instead of solving that again. Below code runs a loop in the string and if at any instant, character is operator then we divide the input from there, recursively solve each part and then combine the result in all possible ways. See the use of c_str() function, this function converts the C++ string into C char array, this function is used in below code because atoi() function expects a character array as an argument not the string. It converts character array to number.
