Hey guys,

I've been asked this in a interview and have been hacking away for days trying to figure out how to code this. The job opportunity is long gone, but my desire to educate myself leads me to ask in desperation for someone to help me code this question. Here tis:

Given any math expression that only has +, -, and * such as
1 + 2 * 3

Write a function to evaluate all possible answers for combinations of parentheses like so...

((1 + 2) * 3) = 9
(1 + (2 * 3)) = 7

It gets much more complicated for 5 or 6 terms just try it.
I broke down the idea into my own incomplete algorithm that by breaking the expression into only 2 terms like for a 5-term expression, you would have
1 and 4 terms
2 and 3 terms
3 and 2 terms
4 and 1 terms

and then you just break it down further everytime your terms > 2. Make sense? I hope so. I know there's got to be some kind of recursion. I've written code to take the expression and tokenize it into 2 arrays, one with the numbers, and the other with operators.

Something like this...
for (int left = 1, int right = numcount - 1; right != 0; left++, right--)
{
// evaluate or break down the left side terms
if (left == 1)
// means the leftans is just the one
else if (left == 2)
// evaluate the 1 + 2 or whatever expression and get the leftans
else if (left > 2)
// here's where i'm stuck, some kind of recursion, multiple left answers

// do the same for the right side terms
if (right == 1)
...

ans = calc(leftans, rightans, operator);
}

The code has to be written in strictly C so no use of some elaborate libraries. Kudos to anyone who can help enlighten me :)