Interesting Programming Problem...

[Xorcist]

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.

[cragwolf]

Step 1: Carry out the ancient task of determining all the permutations of a list of entities (in this case, operators). For example, for the expression:

5 * 6 + 2 - 1

The operator permutations are:

* + -
* - +
+ * -
+ - *
- + *
- * +

or in other words 3! = 3 x 2 x 1

Or with n operators: n! = n * (n-1) * ... * 2 * 1

To generate the list of permutations, use a recursive algorithm. Look it up on the internet, I think it's pretty common.

Step 2: For each permutation, reduce the expression to a single number by going through each operator in the required order one at a time. In the above example, for the permutation * - +, you have the following sequence of steps:

5 * 6 + 2 - 1
30 + 2 - 1
30 + 1
31

Each operator O has a left number L and a right number R. In the above example, * has a left number 5 and a right number 6. So, a reduction step for the ith operator O(i) would involve the following:

O(i-1).R := O(i).Operate;
O(i+1).L := O(i).Operate;
Delete(O(i));

where O(i).Operate adds (or multiplies or subtracts) L and R.

In fact, this problem is so interesting that I might try writing a little program myself.

[cragwolf]

Well, I finished the program. It runs on the command-line, and you'll need FPC to compile it. Tested on Linux only. It essentially uses the algorithm I described in my previous post. The code is ugly but it's reasonably well commented. Download link:

http://www.urbanaustralia.org/cragwolf/expval.tar.gz (2.7 KB)

Well, my 3 days off are over. Back to the toil and drudgery of work. :(

[WILL]

Well now we know who the Algo-Guru of the site is. ;)

[Traveler]

Well now we know who the Algo-Guru of the site is.

Indeed, not only an answer, but a workable codesample too. Impressive!