Xorcist
05-05-2005, 04:26 PM
which I can't seem to solve. :)
Maybe someone here can help.
Given a string expression of a numeric equation, write a function to determine all the various parenthesizations, and display all the unique resulting answers. String expressions will only contain positive integers and the operators for '+', '-', and '*'.
Example: "1 * 2 - 3 + 4"
(((1 * 2) - 3) + 4) = 3
((1 * 2) - (3 + 4)) = -5
((1 * (2 - 3)) + 4) = 3
(1 * ((2 - 3) + 4)) = 3
(1 * (2 - (3 + 4))) = -5
2 unique answers { -5, 3 }
the only part that needs to be printed out is the last line, but the above parenthesizations show the work that would need to be done to find those unique answers.
My question is, how would one go about arranging the various parenthesis. Is there a known algorithm to do this? I have no problem tokenizing the numbers and operators, or even adding them together using a stack. But I can't seem to figure out a good way to cycle through all the orderings of parenthesis.
In fact I don't think the parenthesis are necessary at all in the given problem, just the ordering of operations. Anyone have any advice they can lend me. This problem is driving me nutts.
Maybe someone here can help.
Given a string expression of a numeric equation, write a function to determine all the various parenthesizations, and display all the unique resulting answers. String expressions will only contain positive integers and the operators for '+', '-', and '*'.
Example: "1 * 2 - 3 + 4"
(((1 * 2) - 3) + 4) = 3
((1 * 2) - (3 + 4)) = -5
((1 * (2 - 3)) + 4) = 3
(1 * ((2 - 3) + 4)) = 3
(1 * (2 - (3 + 4))) = -5
2 unique answers { -5, 3 }
the only part that needs to be printed out is the last line, but the above parenthesizations show the work that would need to be done to find those unique answers.
My question is, how would one go about arranging the various parenthesis. Is there a known algorithm to do this? I have no problem tokenizing the numbers and operators, or even adding them together using a stack. But I can't seem to figure out a good way to cycle through all the orderings of parenthesis.
In fact I don't think the parenthesis are necessary at all in the given problem, just the ordering of operations. Anyone have any advice they can lend me. This problem is driving me nutts.