Genera tutte le combinazioni di espressioni matematiche che si aggiungono alla destinazione (compiti/interviste Java)

Question

Ho provato a risolvere il problema di seguito per una sfida di codifica ma non sono riuscito a terminarlo in 1 ora. Ho un'idea su come funziona l'algoritmo ma non sono abbastanza sicuro su come implementarlo al meglio. Ho il mio codice e il problema qui sotto.

I primi 12 cifre di pi sono 314159265358. Possiamo fare queste cifre in una valutazione di espressione per 27182 (prime 5 cifre e) come segue:

3141 * 5/9 * 26/5 * 3 - 5 * 8 = 27182 

o

3 + 1 - 415 * 92 + 65358 = 27182 

Si noti che l'ordine delle cifre di input non è cambiato. Gli operatori (+, -, /, o *) sono semplicemente inseriti per creare l'espressione.

Scrivere una funzione di prendere una lista di numeri e un obiettivo, e restituire tutti i modi che questi numeri possono essere formate in espressioni che valutano al bersaglio

Ad esempio:
f ("314.159.265.358", 27182) deve stampare:

3 + 1 - 415 * 92 + 65358 = 27182 
3 * 1 + 4 * 159 + 26535 + 8 = 27182 
3/1 + 4 * 159 + 26535 + 8 = 27182 
3 * 14 * 15 + 9 + 26535 + 8 = 27182 
3141 * 5/9 * 26/5 * 3 - 5 * 8 = 27182 

Questo problema è difficile dal momento che si può avere qualsiasi combinazione di numeri e non prendere in considerazione un numero alla volta. Non ero sicuro di come fare le combinazioni e la ricorsione per quel passo. Si noti che le parentesi non vengono fornite nella soluzione, tuttavia viene mantenuto l'ordine delle operazioni.

Il mio obiettivo è quello di iniziare con dicono

{"3"} 
then 
{"31", "3+1", "3-1", "3*1" "3/1"} 
then 
{"314", "31+4", "3+1+4", "3-1-4", "31/4", "31*4", "31-4"} etc. 

poi un'occhiata alla ogni valore nella lista ogni volta e vedere se è valore di destinazione. Se lo è, aggiungi quella stringa all'elenco dei risultati.

Ecco il mio codice

public static List<String> combinations(String nums, int target) 
    { 

     List<String> tempResultList = new ArrayList<String>(); 
     List<String> realResultList = new ArrayList<String>(); 
     String originalNum = Character.toString(nums.charAt(0)); 


     for (int i = 0; i < nums.length(); i++) 
     { 
      if (i > 0) 
      { 
       originalNum += nums.charAt(i); //start off with a new number to decompose 
      } 
      tempResultList.add(originalNum); 
      char[] originalNumCharArray = originalNum.toCharArray(); 
      for (int j = 0; j < originalNumCharArray.length; j++) 
      { 
       //go through every character to find the combinations? 
       // maybe recursion here instead of iterative would be easier... 
      } 
      for (String s : tempResultList) 
      { 
       //try to evaluate 
       int temp = 0; 
       if (s.contains("*") || s.contains("/") || s.contains("+") || s.contains("-")) 
       { 
        //evaluate expression 
       } else { 
        //just a number 
       } 
       if (temp == target) 
       { 
        realResultList.add(s); 
       } 

      } 
     tempResultList.clear(); 
     } 
     return realResultList; 
    } 

Potrebbe qualcuno aiutare con questo problema? Alla ricerca di una risposta con codifica in esso, dal momento che ho bisogno di aiuto con la generazione di possibilità

Answer 1

non credo che sia necessario costruire un albero, si dovrebbe essere in grado di calcolare, come si va - è sufficiente per ritardare addizioni e sottrazioni leggermente in modo da poter prendere la precedenza in considerazione in modo corretto:

static void check(double sum, double previous, String digits, double target, String expr) { 
    if (digits.length() == 0) { 
    if (sum + previous == target) { 
     System.out.println(expr + " = " + target); 
    } 
    } else { 
    for (int i = 1; i <= digits.length(); i++) { 
     double current = Double.parseDouble(digits.substring(0, i)); 
     String remaining = digits.substring(i); 
     check(sum + previous, current, remaining, target, expr + " + " + current); 
     check(sum, previous * current, remaining, target, expr + " * " + current); 
     check(sum, previous/current, remaining, target, expr + "/" + current); 
     check(sum + previous, -current, remaining, target, expr + " - " + current); 
    } 
    } 
} 

static void f(String digits, double target) { 
    for (int i = 1; i <= digits.length(); i++) { 
    String current = digits.substring(0, i); 
    check(0, Double.parseDouble(current), digits.substring(i), target, current); 
    } 
} 

Answer 2

In primo luogo, è necessario un metodo in cui è possibile inserire l'espressione

3141 * 5/9 * 26/5 * 3 - 5 * 8 

e ottenere la risposta:

27182 

Successivamente, è necessario creare una struttura ad albero. Il tuo primo e secondo livello sono completi.

3 
31, 3 + 1, 3 - 1, 3 * 1, 3/1 

Al terzo livello mancano alcune espressioni.

31 -> 314, 31 + 4, 31 - 4, 31 * 4, 31/4 
3 + 1 -> 3 + 14, 3 + 1 + 4, 3 + 1 - 4, 3 + 1 * 4, 3 + 1/4 
3 - 1 -> 3 - 14, 3 - 1 + 4, 3 - 1 - 4, 3 - 1 * 4, 3 - 1/4 
3 * 1 -> 3 * 14, 3 * 1 + 4, 3 * 1 - 4, 3 * 1 * 4, 3 * 1/4 
3/1 -> 3/14, 3/1 + 4, 3/1 - 4, 3/1 * 4, 3/1/4 

È possibile interrompere l'aggiunta di foglie a un ramo dell'albero quando una divisione produce un numero intero non.

Come potete vedere, il numero di foglie ad ogni livello del vostro albero aumenterà rapidamente.

Per ogni foglia, è necessario aggiungere il valore successivo, il valore successivo aggiunto, sottratto, moltiplicato e diviso. Come ultimo esempio, qui sono 5 del quarto foglie di livello:

3 * 1 + 4 -> 3 * 1 + 41, 3 * 1 + 4 + 1, 3 * 1 + 4 - 1, 3 * 1 + 4 * 1, 
    3 * 1 + 4/1 

Il codice deve generare 5 espressione lascia per ogni foglia fino a quando non hai utilizzato tutte le cifre di ingresso.

Dopo aver utilizzato tutte le cifre di input, controllare ciascuna equazione foglia per vedere se è uguale al valore.

Answer 3

mio Javascript implementazione:
migliorerà il codice utilizzando operaio web in seguito

// was not allowed to use eval , so this is my replacement for the eval function. 
function evaluate(expr) { 
    return new Function('return '+expr)(); 
} 
function calc(expr,input,target) { 
    if (input.length==1) { 
    // I'm not allowed to use eval, so I will use my function evaluate 
    //if (eval(expr+input)==target) console.log(expr+input+"="+target); 
    if (evaluate(expr+input)==target) document.body.innerHTML+=expr+input+"="+target+"<br>"; 
    } 
    else { 
    for(var i=1;i<=input.length;i++) { 
     var left=input.substring(0,i); 
     var right=input.substring(i); 
     ['+','-','*','/'].forEach(function(oper) { 
     calc(expr+left+oper,right,target); 
     },this); 
    } 
    } 
}; 
function f(input,total) { 
    calc("",input,total); 
}