java - how to find all possible solutions to a formula, like 100*7-8*3+7? (8 Out of 10 Cats Does Countdown solver) -

so fun decided write simple program can solve 8 out of 10 cats countdown number puzzle, link form countdown, same rules. program goes through possible combinations of axbxcxdxexf, letters numbers , "x" +, -, / , *. here code it:

private void combinerecursive( int step, int[] numbers, int[] operations, int combination[]){     if( step%2==0){//even steps numbers         for( int i=0; i<numbers.length; i++){             combination[ step] = numbers[ i];             if(step==10){//last step, 6 numbers , 5 operations placed                 int index = solution.issolutioncorrect( combination, targetsolution);                 if( index>=0){                     solutionqueue.addlast( new solution( combination, index));                 }                 return;             }             combinerecursive( step+1, removeindex( i, numbers), operations, combination);         }     }else{//odd steps operations         for( int i=0; i<operations.length; i++){             combination[ step] = operations[ i];             combinerecursive( step+1, numbers, operations, combination);         }     } } 

and here use test if combination want not.

public static int issolutioncorrect( int[] combination, int targetsolution){     double result = combination[0];     //just test     if( arrays.equals( combination, new int[]{100,'*',7,'-',8,'*',3,'+',7,'+',50})){         system.out.println( "found");     }     for( int i=1; i<combination.length; i++){         if(i%2!=0){             switch( (char)combination[i]){                 case '+': result+= combination[++i];break;                 case '-': result-= combination[++i];break;                 case '*': result*= combination[++i];break;                 case '/': result/= combination[++i];break;             }         }         if( targetsolution==result){             return i;         }     }            return targetsolution==result?0:-1; } 

so in last episode found problem code. solution 1 of puzzles.

(10*7)-(8*(3+7)) 

i noticed find combination "10*7-8*3+7" (twice), because check solutions doing operation left right don't find answers. check solutions ((((10*7)-8)*3)+7). though found combination don't have right order.

so question how test possible math orders, (10*7)-(8*(3+7)), (10*7)-((8*3)+7) or 10*(7-8)*(3+7)? though can use balance tree operations balancing nodes. still have not idea how go through possible combinations without moving around formula.

(10*7)-(8*(3+7))           -      /        \     *         *   /   \      /  \ 700   7     8    +                 / \               7    3  (10*7)-((8*3)+7)           -      /        \     *         +   /   \      /  \ 700   7     *    7            / \           8  3  10*(7-8)*(3+7)                   *            /           \           *      /        \         10     -          +   /   \      /  \ 7     8     3    7 

how do in code? not looking solved code more of how should change perspective fix it. don't know why stumped @ it.

about me: 4th year computer science, not new or noob @ programming (i believe @ least ;))

this easier solved dedicated class represents expression, , not array. can enumerate possible trees. mix of another answer wrote similar task, , answer shows how generate binary trees gave this:

import java.util.arraylist; import java.util.arrays; import java.util.list;  public class numberpuzzlewithcats {     public static void main(string[] args)     {         list<integer> numbers = arrays.aslist(10,7,8,3,7);         solve(numbers);     }      private static void solve(list<integer> numbers)     {         list<node> nodes = new arraylist<node>();         (int i=0; i<numbers.size(); i++)         {             integer number = numbers.get(i);             nodes.add(new node(number));         }         system.out.println(nodes);         list<node> = create(nodes);         system.out.println("found "+all.size()+" combinations");           (node node : all)         {             string s = node.tostring();             system.out.print(s);             if (s.equals("((10*7)-(8*(3+7)))"))             {                 system.out.println(" <--- there is :)");             }             else             {                 system.out.println();             }         }     }      private static list<node> create(node n0, node n1)     {         list<node> nodes = new arraylist<node>();         nodes.add(new node(n0, '+', n1));         nodes.add(new node(n0, '*', n1));         nodes.add(new node(n0, '-', n1));         nodes.add(new node(n0, '/', n1));         nodes.add(new node(n1, '+', n0));         nodes.add(new node(n1, '*', n0));         nodes.add(new node(n1, '-', n0));         nodes.add(new node(n1, '/', n0));         return nodes;     }      private static list<node> create(list<node> nodes)     {         if (nodes.size() == 1)         {             return nodes;         }         if (nodes.size() == 2)         {             node n0 = nodes.get(0);             node n1 = nodes.get(1);             return create(n0, n1);         }         list<node> nextnodes = new arraylist<node>();         (int i=1; i<nodes.size()-1; i++)         {             list<node> s0 = create(nodes.sublist(0, i));             list<node> s1 = create(nodes.sublist(i, nodes.size()));             (node n0 : s0)             {                 (node n1 : s1)                 {                     nextnodes.addall(create(n0, n1));                 }             }         }         return nextnodes;     }      static class node     {         int value;         node left;         character op;         node right;          node(node left, character op, node right)         {             this.left = left;             this.op = op;             this.right = right;         }         node(integer value)         {             this.value = value;         }          @override         public string tostring()         {             if (op == null)             {                 return string.valueof(value);             }             return "("+left.tostring()+op+right.tostring()+")";         }     } } 

it print combinations created, including 1 have been looking for:

[10, 7, 8, 3, 7] found 16384 combinations (10+(7+(8+(3+7)))) (10*(7+(8+(3+7)))) ... ((10*7)+(8*(3+7))) ((10*7)*(8*(3+7))) ((10*7)-(8*(3+7))) <--- there is :) ((10*7)/(8*(3+7))) ((8*(3+7))+(10*7)) ... ((7/3)-((8/7)/10)) ((7/3)/((8/7)/10)) 

of course, checking whether right solution found comparing string representations ... "very pragmatic", state way, think actual approach of generation important here.

(i hope have been looking - not view site linked to...)