这个递归回溯解决方案如何解决算术表达式?
How does this recursive-backtrack solution work for solving arithmetic-expression?
我正在尝试解决这个算术表达式问题
我在数组中取 n(此处为 5)个元素,并尝试 (+ - *) 中运算符的所有组合以查找表达式是否可被 101 整除
在这里,我们不关心运算符的顺序......不使用 BODMAS
输入
5
55 3 45 33 25
输出
55+3-45*33-25
我是递归和回溯方面的新手。我试图了解问题的哪一部分是错误的
这是我的代码:
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 未反映操作员之前尝试恢复。
请帮忙..我们将不胜感激...
你的回溯方法有问题。
您执行 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
因此,您应该将 res
和 num1
传递给 performBackTrack
,而不是 num1
和 num2
。
除此之外,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
和returns true
.
编辑:
其实这样简单多了。你不需要 performBackTrack
。
只需替换
nums[index+1]=performBackTrack(op,num1,num2); //restoring number
和
nums[index+1]=num2;
毕竟,您正在尝试向 nums[index+1]
分配它在分配 nums[index+1]=res;
之前的值,这恰好是 num2
.
我正在尝试解决这个算术表达式问题 我在数组中取 n(此处为 5)个元素,并尝试 (+ - *) 中运算符的所有组合以查找表达式是否可被 101 整除 在这里,我们不关心运算符的顺序......不使用 BODMAS 输入
5
55 3 45 33 25
输出
55+3-45*33-25
我是递归和回溯方面的新手。我试图了解问题的哪一部分是错误的
这是我的代码:
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 未反映操作员之前尝试恢复。
请帮忙..我们将不胜感激...
你的回溯方法有问题。
您执行 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
因此,您应该将 res
和 num1
传递给 performBackTrack
,而不是 num1
和 num2
。
除此之外,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
和returns true
.
编辑:
其实这样简单多了。你不需要 performBackTrack
。
只需替换
nums[index+1]=performBackTrack(op,num1,num2); //restoring number
和
nums[index+1]=num2;
毕竟,您正在尝试向 nums[index+1]
分配它在分配 nums[index+1]=res;
之前的值,这恰好是 num2
.