Wie funktioniert diese rekursive Backtrack-Lösung zum Lösen von arithmetischen Ausdrücken?

Question

Ich versuche, dieses arithmetische Ausdruck Problem zu lösen wo ich n (hier 5) Elemente in einem Array und versuchen Sie alle Kombination von Operatoren in (+ - *) zu finden, wenn der Ausdruck durch 101 teilbar ist Hier sind wir nicht mit der Reihenfolge der operators..not BODMAS Eingangs

Output

55 + 3-45 * 33-25

Verwendung betroffenen

Ich bin neu bei Rekursion und Backtracking. Ich versuche, die einen Teil des Problems zu verstehen ist falsch

Hier ist mein Code:

public static boolean solve(char []operators,long[]nums,long res,int index,Stack<Character>st){ 


    if(index+1==nums.length){ //reached end of number array 
     if(res%101==0){ 
      System.out.println(res); 
      return true; 
     } 
     return false; 
    } 

    for(int i=0;i<operators.length;i++){ 
     char op=operators[i]; //try the operator 
     long num1=nums[index]; 
     long num2=nums[index+1]; //LINE1 

     System.out.println("trying "+num1+""+op+" num2="+num2); 
     res=performOp(op,num1,num2); 
     nums[index+1]=res; 

     st.push(op); 
     if(solve(operators,nums,res,index+1,st)){ 
      return true; 
     } 
     //backtrack 
     //return to earlier state than try another operator 

     //LINE2 
     nums[index+1]=performBackTrack(op,num1,num2); //restoring number 
     System.out.println("num2="+num2+" num1="+num1+" after backtrack"); 
     st.pop(); 

    } 

    return false; 
} 

    public static long performBackTrack(char op,long num1,long num2){ 
    //trying to restore numbers 
    switch(op){ 
     case '+':return num2-num1; 
     case '-':return num1-num2; 
     case '*':return num1/num2; 
     default:return 0L; 
    } 
} 

public static long performOp(char op,long num1,long num2){ 
    switch(op){ 
     case '+':return num1+num2; 
     case '-':return num1-num2; 
     case '*':return num1*num2; 
     default:return 0L; 
    } 
} 

Hier nach Rückzieher, wenn ich Änderungen an LINE2 machen und innerhalb der Schleife gehen nächste Operator, die Änderungsarbeiten zu versuchen, Gut, wenn ich die ursprüngliche Nummer an LINE2 zurückbekomme, aber sie wird nicht an LINE1 reflektiert, die letzte Nummer, die ich versuche, wiederherzustellen, bevor ich einen Operator ausprobiere, wird nicht in LINE1 wiedergegeben.

Bitte help..Any Art von Hilfe geschätzt wird ...

Answer 1

Sie haben einen Fehler in Ihrer Back-Tracking-Methode.

Sie res=performOp(op,num1,num2) durchführen und das Ergebnis nums[index+1] zuweisen.

Lassen Sie uns alle möglichen Operationen berücksichtigen und wie sie umgekehrt:

res = num1 + num2  -> num2 = res - num1 
res = num1 - num2  -> num2 = num1 - res 
res = num1 * num2  -> num2 = res/num1 

Daher Sie res und num1-performBackTrack, nicht num1 und num2 passieren sollte.

Abgesehen davon, performBackTrack sollte wie folgt aussehen:

public static long performBackTrack(char op,long res,long num1) { 
//trying to restore numbers 
    switch(op){ 
     case '+':return res - num1; 
     case '-':return num1 - res; 
     case '*':return res/num1; 
     default:return 0L; 
    } 
} 

und der Aufruf von performBackTrack sein sollte:

nums[index+1]=performBackTrack(op,res,num1); 

Dies erzeugt (für die gegebene Eingabe) die folgende Ausgabe:

trying 55+ num2=3 
trying 58+ num2=45 
trying 103+ num2=33 
trying 136+ num2=25 
num2=25 num1=136 after backtrack 
trying 136- num2=25 
num2=25 num1=136 after backtrack 
trying 136* num2=25 
num2=25 num1=136 after backtrack 
num2=33 num1=103 after backtrack 
trying 103- num2=33 
trying 70+ num2=25 
num2=25 num1=70 after backtrack 
trying 70- num2=25 
num2=25 num1=70 after backtrack 
trying 70* num2=25 
num2=25 num1=70 after backtrack 
num2=33 num1=103 after backtrack 
trying 103* num2=33 
trying 3399+ num2=25 
num2=25 num1=3399 after backtrack 
trying 3399- num2=25 
num2=25 num1=3399 after backtrack 
trying 3399* num2=25 
num2=25 num1=3399 after backtrack 
num2=33 num1=103 after backtrack 
num2=45 num1=58 after backtrack 
trying 58- num2=45 
trying 13+ num2=33 
trying 46+ num2=25 
num2=25 num1=46 after backtrack 
trying 46- num2=25 
num2=25 num1=46 after backtrack 
trying 46* num2=25 
num2=25 num1=46 after backtrack 
num2=33 num1=13 after backtrack 
trying 13- num2=33 
trying -20+ num2=25 
num2=25 num1=-20 after backtrack 
trying -20- num2=25 
num2=25 num1=-20 after backtrack 
trying -20* num2=25 
num2=25 num1=-20 after backtrack 
num2=33 num1=13 after backtrack 
trying 13* num2=33 
trying 429+ num2=25 
num2=25 num1=429 after backtrack 
trying 429- num2=25 
404 

und gibt true.

EDIT:

Eigentlich ist dies viel einfacher. Sie brauchen nicht. Ersetzen Sie einfach

nums[index+1]=performBackTrack(op,num1,num2); //restoring number 

mit

nums[index+1]=num2; 

Immerhin Sie versuchen, nums[index+1] den Wert zuweisen, dass es vor der Zuweisung hatte nums[index+1]=res;, die gerade num2 ist.