algorithm - How to print the calculated process of a game like 24point? -

this question has answer here:

• writing algorithm decide whether target number can reached set of other numbers , specific operators? 3 answers

here's problem: given 4 numbers, need give calculated process results 24. operations can use addition, subtraction, multiplication, division. how print calculated process? ex: input: 4,7,8,8 output: (7-(8/8))*4=24.

(the following expansion on idea suggested sayakiss)

one option enumerating possible combinations of numbers , arithmetic operations performed on them.

if have 4 numbers, there 24 different ways write them in list (the following example numbers 4, 7, 8, 9 - changed last number in example make them different):

4 7 8 9 4 7 9 8 4 8 7 9 4 8 9 7 ... 9 8 7 4 

if numbers identical, of above lists appear twice (not problem).

for each of above orderings, there 64 different ways insert arithmetic operation between numbers:

4+7+8+9 4+7+8-9 4+7+8*9 4+7+8/9 4+7-8+9 ... 4/7/8/9 

for each of above sequences, there 5 ways place parentheses:

((4-7)-8)-9 (4-7)-(8-9) (4-(7-8))-9 4-((7-8)-9) 4-(7-(8-9)) 

when combine 3 "aspects" mentioned above, 24 * 64 * 5 = 7680 expressions; evaluate each 1 , check whether value 24 (or whatever number need be).

it may convenient generate expressions in tree form, simplify evaluation (this depends on programming language want use; e.g. in c/c++ there no eval function) . example, expression 4*((7-8)+9) may represented following tree:

  *  / \ 4   +    / \   -   9  / \ 7   8 

some notes:

• you may want tweak choice of arithmetic operations allow expressions 47+88 - not sure whether rules of game permit that.
• many of evaluated expressions may annoyingly verbose, ((4+7)+8)+8 , 4+(7+(8+8)) (which examined twice, order of 8's switched); prevent inserting dedicated checks algorithm.