java - 递归 - 评估目标的表达式

Question

我正在尝试理解递归并解决问题

运算符 = ['','*', "+"]
输入:“2224”
目标:24
输出 = {"22+2", "2+22", "24"}

这是我想出的代码。但它会产生无效输出。

static List<String> output = new ArrayList<>();

static String[] generate_all_expressions(String s, long target) {
    getExpressionsRecur(s, target, 0, null, 0);
    String[] out = new String[output.size()];       
    return output.toArray(out);
}
static void getExpressionsRecur(String s, long target, int currentValue, String currExpression, int currIndex) {

    if (currIndex == s.length()){
        if (currentValue == target) {
            output.add(currExpression);
        }
        return;
    }
    if (currentValue == target) {
        output.add(currExpression);
        return;
    } 
    int currentPart = Integer.valueOf(s.substring(currIndex, currIndex+1));
    if (currIndex == 0) {
        getExpressionsRecur(s, target, currentPart, String.valueOf(currentPart), currIndex+1);
    } else {
        int value = Integer.valueOf(String.valueOf(currentValue) + String.valueOf(currentPart));
        getExpressionsRecur(s, target, value , currExpression + "" + currentPart,  currIndex+1);
        getExpressionsRecur(s, target, (currentValue * currentPart), currExpression + "*" + currentPart,  currIndex+1);
        getExpressionsRecur(s, target, (currentValue + currentPart), currExpression + "+" + currentPart,  currIndex+1);

    }
}

它产生: {22+2, 2*2+2*4, 2+2+2*4}

谁能帮我找出错误？

Answer 1

首先重新考虑您的递归，因为您并没有解决所有问题。

如果需要，写出案例，也许从 3 位数开始，因为案例较少；例如，在您的代码中，“24”永远不会被单独评估。

您错误地计算了串联情况下的值。 22*2 将变为 22*24。但是您是说这个新表达式的值为 444(应该是 528)。你不能真正使用当前值。也许您可以重组递归以使其更容易。

您可以使用我放在一起的这个 Expression 对象来替换您的表达式 String... 根据需要调用 expression.toString() 和 expression.value()。但是，即使在实现了这个或类似的表达式对象之后，您仍然需要对基本递归结构进行更改。

public class Expression{
    Expression lExpression;
    String lValue;
    Expression rExpression;
    String operator;

    public Expression(String expression) {
        int multIndex = expression.indexOf("*");
        int addIndex = expression.indexOf("+");
        if(multIndex == -1 && addIndex == -1) { 
            this.lExpression = new Expression(Integer.valueOf(expression));
            return;
        }

        if(multIndex != -1 && multIndex < addIndex) {

            this.lExpression = new Expression(expression.substring(0, addIndex));
            this.operator = expression.substring(addIndex, addIndex+1);
            this.rExpression = new Expression(expression.substring(addIndex+1));
        }else {
            if(addIndex == -1) { 
            addIndex = Integer.MAX_VALUE;

        } 
        if(multIndex == -1) { 
            multIndex = Integer.MAX_VALUE;
        }
            int opIndex = multIndex < addIndex ? multIndex : addIndex; 
            this.lExpression = new Expression(expression.substring(0, opIndex));
            this.operator = expression.substring(opIndex, opIndex+1);
            this.rExpression = new Expression(expression.substring(opIndex+1));         }



    }
    public Expression(int value) {
        this.lValue = String.valueOf(value);
        this.lExpression = null;
        this.rExpression = null;
        this.operator = null;
    }

    @Override
    public String toString() {
        return (lExpression!=null ? lExpression : lValue) + (operator !=null ? operator: "") +  (rExpression!=null ? rExpression : "");

    }

    public int value() {
        if(lExpression == null) {
            return Integer.valueOf(lValue);
        }
        if("*".equals(operator)) {
            return lExpression.value() * rExpression.value() ;
        }
        if("+".equals(operator)) {
            return lExpression.value() + rExpression.value();
        }
        return lExpression.value();
    }