Theory behind Implementation of a Challenge 24 Solver

As an introduction to Java and android development I decided to write a Challenge 24 (given 4 numbers, must add, multiply, divide or subtract in order to create the product 24) solving application that implements an exhaustive technique to solve for any and all possible solutions. currently it works like so (a,b,c,d being the 4 input numbers)

((a+b)+c)+d
((a+b)+c)-d
((a+b)+c)*d
((a+b)+c)/d
((a+b)-c)+d
...
...
((a/b)/c)/d
((a+b)+d)+c
((a+b)+d)-c

and so on...开发者_C百科

I have found this works on a vast majority of cases, however cases such as 8,3,8,3 came up in testing where no solutions were found, however the solution 8/(3-8/3)=24 is correct. So I guess the end question is fairly vague, but how could this be implemented to account for cases where parentheses are crucial to finding a solution?

If you want to continue to be exhaustive, create conditions for each possible combination of parentheses.

I would approach this by enumerating the possible operator/operand combinations in a prefix or postfix notation, or building an expression tree. That should make it easier to express them in loops and/or functions. Then you can convert the solutions to infix for output; that's very simple if you're not concerned about superfluous parentheses.

There may be optimizations you could make to the search order that way, but the problem space is so small I wouldn't bother.

Consider variables a,b,c,d as inputs, and +,-,*,/ as operators

you will always have three operators

a op b op c op d

Now consider the combinations of parens

1 group of 2
(a op b) op c op d
a op (b op c) op d
a op b op (c op d)

1 group of 3
(a op b op c) op d
a op (b op c op d)

each 3 can be comprised 
(x op y op z) as above example
(x op (y op z))
((x op y) op z)

Also, 2 groups of 2
(a op b) op (c op d)

Now, you must test each combination above with each set of operations:

 Haha silly code parser, you think these are comments in here... tsk tsk
 +++, ++-, ++*, ++/, +-+, +--, +-*, +-/,
 +*+, +*-, +**, +*/, +/+, +/-, +/*, +//,
 -++, -+-, -+*, -+/, --+, ---, --*, --/,
 -*+, -*-, -**, -*/, -/+, -/-, -/*, -//,
 *++, *+-, *+*, *+/, *-+, *--, *-*, *-/,
 **+, **-, ***, **/, */+, */-, */*, *//,
 /++, /+-, /+*, /+/, /-+, /--, /-*, /-/,
 /*+, /*-, /**, /*/, //+, //-, //*, ///

So, test each group of twos with those operations, each group of threes (including the simple version and the nested versions), and the one with two groups of two.

By my estimates, that's 640 tests.

This can be logically reduced, for example if op1 == op2 == op3 then the parenthesis do not matter. There are other reductions you can make too.

Edit: You would then need to run over each permutation of a,b,c,d which would bring the total up to 15,360 (less if there are duplicates, of course.)