この再帰バックトラックソリューションは、算術式を解くためにどのように機能しますか？

Question

私はこの算術式の問題を解決しようとしています ここでは、配列内のn個（ここでは5個）の要素をとり、式が101で割り切れるかどうかを調べるために（+ - *）の演算子のすべての組み合わせを試します。 BODMAS 入力

出力

55 + 3-45 * 33から25

を使用operators..notの順序に関係ありません

私は再帰とバックトラック時に新しいです。私はここに私のコードだ

間違っている問題のどの部分を理解しようとしています：

ここ

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; 
    } 
} 

、私はLINE2に変更を加えて、次の作業をしようとするループ内に行くとき、変更の作品をバックトラックした後、私はLINE2で信号番号を取り戻すが、それはLINE1に反映されていないので、LINE1に反映されていないオペレータを試す前に復元しようとする最後の番号。ヘルプの

くださいhelp..Anyの種類は、あなたがあなたのバックトラッキング方法のバグを持っている...

Answer 1

を理解されるであろう。

res=performOp(op,num1,num2)を実行し、nums[index+1]の結果を割り当てます。

はのは、すべての可能な操作を考えると、それらを逆にする方法：

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

したがって、あなたがいないnum1とnum2、performBackTrackにresとnum1を渡す必要があります。

それに加えて、performBackTrackは次のようになります。

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; 
    } 
} 

とperformBackTrackへの呼び出しは次のようになります。

：

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

これは、（自分の与えられた入力のための）次の出力を生成します

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 

を返し、trueを返します。

EDIT：

は実は、これははるかに簡単です。 performBackTrackは必要ありません。 はちょうどあなたがnums[index+1]に、それは正確にnum2で割り当てnums[index+1]=res;、前に持っていた値を代入しようとしている、すべての後

nums[index+1]=num2; 

で

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

を交換してください。