使用括号求出表达式的最小值和最大值

Question

我有一个没有括号的一行表达式，例如1+5*6-3。我们可以使用所有的运算符(+，-，*，/)。我需要知道什么？当我们可以使用括号时，表达式的最大值和最小值是什么。

示例

1)

输入：1+5*6-3

输出：33 16

说明：33 = (((1+5)*6)-3) = 16 = (1+(5*(6-3))

2)

输入：15*5-12-9

输出：72 -240

3)

输入：3*10*16-14-11*2

输出：954 -600

4)

输入：8-5*18+5-13+0*2+14-6*6+1

输出：7233 -13482

5)

输入：6+5-15*18+14-3-5-3-2-2*8-14+12

输出：11081 -4935

6)

输入：13-4*6*18+12+8-5*8-4+2+11*6+9-7+6*12*18+8-7+3*1-15*1-12*1-12-14+7-14*9*6

输出：74388962089190 -72949270802716

我为什么要写这篇文章？我有快速算法，但它适用于测试编号1、2、3，但对于4、5、6则得到了糟糕的结果。为什么？也许你会发现我做错了什么。这是我的代码：

public static long[] parenthesis(String expression, int start, int end) {
    if(resultStorage[start][end][2] == 1) 
        return resultStorage[start][end];

    if(isNumber(expression)) 
        return new long[] { Long.parseLong(expression), Long.parseLong(expression), 1 };

    long[] result = { Integer.MAX_VALUE, Integer.MIN_VALUE, 1 };
    for(int i = 1; i < expression.length() - 1; i++) {
        if(Character.isDigit(expression.charAt(i))) 
            continue;

        long[] left = parenthesis(expression.substring(0, i), start, start + i);
        long[] right = parenthesis(expression.substring(i + 1, expression.length()), start + i + 1, end);
        switch(expression.charAt(i)) {
            case '+' : result[0] = Math.min(result[0], left[0] + right[0]);
                       result[1] = Math.max(result[1], left[1] + right[1]); 
                       break;
            case '-' : result[0] = Math.min(result[0], left[0] - right[0]);
                       result[1] = Math.max(result[1], left[1] - right[1]); 
                       break;
            case '*' : result[0] = Math.min(result[0], left[0] * right[0]);
                       result[1] = Math.max(result[1], left[1] * right[1]); 
                       break;
            case '/' : if(right[0] != 0) 
                           result[0] = Math.min(result[0], left[0] / right[0]);
                       if(right[1] != 0)
                           result[1] = Math.max(result[1], left[1] / right[1]); 
                       break;
        }
    }

    resultStorage[start][end] = result;
    return result;
}

Answer 1

为了理解这个问题，我不得不写我自己的解决方案。我的解决方案没那么快，所以没必要公开。然而，您的解决方案并非在所有情况下都有效的原因是，它不足以使用

new min = min left <op> min right
... analog for new max ...

因为一些最小操作数与一些操作数(我怀疑是减法和除法)结合在一起会产生更大的结果，反之亦然。因此，必须检查所有min/max的左/右组合，以确定新的min和新的最大值：

new min = min left <op> min right
new min = min left <op> max right
new min = max left <op> min right
new min = max left <op> max right
... analog for new max ...

因此，我在代码中引入了两个嵌套循环来完成以下操作：

public static void main(String[] args) {
    parenthesis("1+5*6-3");
    parenthesis("15*5-12-9");
    parenthesis("3*10*16-14-11*2");
    parenthesis("8-5*18+5-13+0*2+14-6*6+1");
    parenthesis("6+5-15*18+14-3-5-3-2-2*8-14+12");
    parenthesis("13-4*6*18+12+8-5*8-4+2+11*6+9-7+6*12*18+8-7+3*1-15*1-12*1-12-14+7-14*9*6");
}

private static void parenthesis(String expression) {
    resultStorage = new long[100][100][100];
    long[] results = parenthesis(expression, 0, 0);
    System.out.println("=====> " + expression + " -> " + results[0] + "/" + results[1]);
}

private static long[][][] resultStorage;

public static long[] parenthesis(String expression, int start, int end) {
    if (resultStorage[start][end][2] == 1)
        return resultStorage[start][end];

    try {
        long parsedLong = Long.parseLong(expression);
        return new long[] { parsedLong, parsedLong, 1 };
    } catch (NumberFormatException e) {
        //
    }

    long[] result = { Integer.MAX_VALUE, Integer.MIN_VALUE, 1 };
    for (int i = 1; i < expression.length() - 1; i++) {
        if (Character.isDigit(expression.charAt(i)))
            continue;
        long[] left = parenthesis(expression.substring(0, i), start, start + i);
        long[] right = parenthesis(expression.substring(i + 1, expression.length()), start + i + 1, end);
        for (int li = 0; li < 2; li++) {
            for (int ri = 0; ri < 2; ri++) {
                switch (expression.charAt(i)) {
                case '+':
                    result[0] = Math.min(result[0], left[li] + right[ri]);
                    result[1] = Math.max(result[1], left[li] + right[ri]);
                    break;
                case '-':
                    result[0] = Math.min(result[0], left[li] - right[ri]);
                    result[1] = Math.max(result[1], left[li] - right[ri]);
                    break;
                case '*':
                    result[0] = Math.min(result[0], left[li] * right[ri]);
                    result[1] = Math.max(result[1], left[li] * right[ri]);
                    break;
                case '/':
                    if (right[ri] != 0)
                        result[0] = Math.min(result[0], left[li] / right[ri]);
                    if (right[ri] != 0)
                        result[1] = Math.max(result[1], left[li] / right[ri]);
                    break;
                }
            }
        }
    }

    resultStorage[start][end] = result;
    return result;
}

这会产生您想要的结果：

=====> 1+5*6-3 -> 16/33
=====> 15*5-12-9 -> -240/72
=====> 3*10*16-14-11*2 -> -600/954
=====> 8-5*18+5-13+0*2+14-6*6+1 -> -13482/7233
=====> 6+5-15*18+14-3-5-3-2-2*8-14+12 -> -4935/11081
=====> 13-4*6*18+12+8-5*8-4+2+11*6+9-7+6*12*18+8-7+3*1-15*1-12*1-12-14+7-14*9*6 -> -72949270802716/74388962089190

我真正感兴趣的是，这个优化是做什么的：

if (resultStorage[start][end][2] == 1)
        return resultStorage[start][end];

在没有resultStorage的情况下，代码运行得很好。但是，这种递归结束条件使它在不丢失结果的情况下非常快。我很高兴听到它是如何工作的..。

编辑:好的，优化似乎终止于已经计算的结果。然而，作为一个怀疑论者，我希望看到这个词带有偏执，把它扔进我的计算器。因此，我对代码又做了两个修改：(1)通过返回已经计算过的表达式的结果，但是使用HashMap表达式-> results (2)用偏执来计算结果项。

下面是：

public static void main(String[] args) {
    parenthesisOuter("1+5*6-3");
    parenthesisOuter("15*5-12-9");
    parenthesisOuter("3*10*16-14-11*2");
    parenthesisOuter("8-5*18+5-13+0*2+14-6*6+1");
    parenthesisOuter("6+5-15*18+14-3-5-3-2-2*8-14+12");
    parenthesisOuter("13-4*6*18+12+8-5*8-4+2+11*6+9-7+6*12*18+8-7+3*1-15*1-12*1-12-14+7-14*9*6");
    parenthesisOuter("1/0");
    parenthesisOuter("1/1-1");
}

private static void parenthesisOuter(String expression) {
    Object[] results = parenthesis(expression);
    System.out.println(expression + " -> " + results[MINVAL] + "=" + results[MINEXPR] + " "
            + results[MAXVAL] + "=" + results[MAXEXPR]);
}

private static Map<String, Object[]> resultMap = new HashMap<>();

private static final int MINVAL = 0;
private static final int MAXVAL = 1;
private static final int MINEXPR = 2;
private static final int MAXEXPR = 3;

public static Object[] parenthesis(String expression) {
    Object[] result = resultMap.get(expression);
    if (result != null) {
        return result;
    }

    try {
        Long parsedLong = new Long(expression);
        return new Object[] { parsedLong, parsedLong, expression, expression };
    } catch (NumberFormatException e) {
        // go on, it's not a number
    }

    result = new Object[] { Long.MAX_VALUE, Long.MIN_VALUE, null, null };
    for (int i = 1; i < expression.length() - 1; i++) {
        if (Character.isDigit(expression.charAt(i)))
            continue;
        Object[] left = parenthesis(expression.substring(0, i));
        Object[] right = parenthesis(expression.substring(i + 1, expression.length()));
        doOp(result, (Long) left[MINVAL], expression.charAt(i), (Long) right[MINVAL],
                (String) left[MINEXPR], (String) right[MINEXPR]);
        doOp(result, (Long) left[MINVAL], expression.charAt(i), (Long) right[MAXVAL],
                (String) left[MINEXPR], (String) right[MAXEXPR]);
        doOp(result, (Long) left[MAXVAL], expression.charAt(i), (Long) right[MINVAL],
                (String) left[MAXEXPR], (String) right[MINEXPR]);
        doOp(result, (Long) left[MAXVAL], expression.charAt(i), (Long) right[MAXVAL],
                (String) left[MAXEXPR], (String) right[MAXEXPR]);
    }

    resultMap.put(expression, result);
    return result;
}

private static void doOp(Object[] result, Long left, char op, Long right, String leftExpression,
        String rightExpression) {
    switch (op) {
    case '+':
        setResult(result, left, op, right, left + right, leftExpression, rightExpression);
        break;
    case '-':
        setResult(result, left, op, right, left - right, leftExpression, rightExpression);
        break;
    case '*':
        setResult(result, left, op, right, left * right, leftExpression, rightExpression);
        break;
    case '/':
        if (right != 0) {
            setResult(result, left, op, right, left / right, leftExpression, rightExpression);
        }
        break;
    }
}

private static void setResult(Object[] result, Long left, char op, Long right, Long leftOpRight,
        String leftExpression, String rightExpression) {
    if (result[MINEXPR] == null || leftOpRight < (Long) result[MINVAL]) {
        result[MINVAL] = leftOpRight;
        result[MINEXPR] = "(" + leftExpression + op + rightExpression + ")";
    }
    if (result[MAXEXPR] == null || leftOpRight > (Long) result[MAXVAL]) {
        result[MAXVAL] = leftOpRight;
        result[MAXEXPR] = "(" + leftExpression + op + rightExpression + ")";
    }
}

这显示了(最后两个看它是否是零安全的)：

1+5*6-3 -> 16=(1+(5*(6-3))) 33=(((1+5)*6)-3)
15*5-12-9 -> -240=(15*((5-12)-9)) 72=((15*5)-(12-9))
3*10*16-14-11*2 -> -600=(3*(10*((16-14)-(11*2)))) 954=(((3*(10*16))-(14-11))*2)
8-5*18+5-13+0*2+14-6*6+1 -> -13482=(((((8-(5*(18+5)))-(13+0))*(2+14))-6)*(6+1)) 7233=(8-(5*(18+(((5-((13+0)*(2+14)))-6)*(6+1)))))
6+5-15*18+14-3-5-3-2-2*8-14+12 -> -4935=(6+((5-(15*((18+(14-((((3-5)-3)-2)-2)))*8)))-(14+12))) 11081=(6+(5-(15*((18+(14-((((3-5)-3)-2)-2)))*(8-(14+12))))))
13-4*6*18+12+8-5*8-4+2+11*6+9-7+6*12*18+8-7+3*1-15*1-12*1-12-14+7-14*9*6 -> -72949270802716=((((((((((13-4)*(6*(18+(12+8))))-5)*(((8-4)+(2+11))*(6+9)))-7)+6)*(12*(18+8)))-7)+3)*(1-(15*((1-(12*(((1-12)-(14+7))-14)))*(9*6))))) 74388962089190=((((13-4)*(6*(18+(12+8))))-5)*(((((8-((4+(2+11))*(6+9)))-(7+6))*(12*(18+8)))-(7+3))*(1-(15*((1-(12*(((1-12)-(14+7))-14)))*(9*6))))))
1/0 -> 9223372036854775807=null -9223372036854775808=null
1/1-1 -> 0=((1/1)-1) 0=((1/1)-1)