CareerCup

(3/3) + 1 + 6

6+3-(1%3)

Write out 24 permutations. Eliminate the permutations that break the equation.

(3+1)/3*6 = 8

What if the expression has more than 4 elements?

This is just an example. The expression has more than 4 operands.

I get it.

const int TOTALOPS = 4;
string expr[exprLength] = {"6","7"...};
string operators[TOTALOPS] = {"+","-","*","/"};

We know that we need (exprLength - 1) operators. Each operator can be {+,-,*,/}

void generate(int index, int maxOps, string opCum[maxOps])
{
if (index == maxOps) //We have filled up operators[]
{
Check these operators against expr
}
else{

for (int op = 0; op < TOTALOPS; ++op)
{

opCum[index] = operators[op];
generate(index + 1, maxOps, opCum);

} //for

} //else
} //generate

The complexity of the above algorithm is 4^N

Here is a backtracking algorithm. It will terminate as soon it found a solution.

bool generate(int index, int maxOps, string opCum[maxOps])
{
if (index == maxOps) //We have filled up operators[]
{
return true if we found the solution.
return false otherwise.
}
else{
for (int op = 0; op < TOTALOPS; ++op)
{
opCum[index] = operators[op];
bool isSuccess = generate(index + 1, maxOps, opCum);
if (isSuccess)
return true;
} //for
} //else

return false;
} //generate

Khoa, your solution is incorrect. Your backtracking algorithm assigns only the operators, but how about parentheses? I assume when index==maxOps, you will evaluate the expression iteratively from left to right? Then, you will miss such cases as (3+1)*(3+6)

Yup! My code doesn't handle parentheses. Any suggestions?
I think generating all possible infix or postfix expressions would be another solution but I don't know how to do that.

(3 + 1) / (3 / 6)

pls give me explanation how does ((3+1)/3)*6 & (3+1)/3*6

(3+1)*(6/3)

(3+1)/(3/6) = 8

((3+1)/3)*6=8

((3+1)/3)*6=8

3 + 1 + 3 + 6 >= 8

(3-1)^(SQRT (3+6))

((3-1)%3)+6 =8

((3-1)%3)+6 =8

the original problem did not rule out other operations. before i saw this post, the answer I had made was:

( 3 - 1 ) ^ -( 3 - 6) = 8

eg., 2^3 = 8

(3 + 1) / (3 / 6) = 4 / 0.5 = 8

(3 + 1) / (3 / 6) = 4 / 0.5 = 8

(3+1)*(3/6)=8

How About This For An Answer:

3! + (-1+6) -3 = 8

3/ -(1-3)*6=8

3 - 1 ^ 3 + 6 = 8

3 - 1 ^ 3 + 6 = 8

3! * 1 / 3 + 6 = 8

((3 << 1) / 3) + 6 = 8