java - 使用括号获取表达式的最小值和最大值

标签 java algorithm recursion parentheses

我有一个没有括号的单行表达式，例如 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;
}

最佳答案

我必须编写自己的解决方案才能理解问题。我的解决方案不是那么快，因此无需公开。但是，您的解决方案并非在所有情况下都有效的原因是，它不足以使用

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

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

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 Expression->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)

关于java - 使用括号获取表达式的最小值和最大值，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33438002/

上一篇：java - 在浏览器中点击应用程序时 Play Framework 挂起

下一篇：java - 生成长椅随机座位表的最有效算法？

相关文章：

haskell - 在递归调用中向后传播信息

java - gettext-common 示例不起作用

java - 如何从 Hibernate session 中分离所有对象

algorithm - 图的 O(m+n) 时间算法

c# - 从每个用户提供的时间列表中找到所有共同时间

sql-server - SQL Server 中可以递归调用存储过程吗？

c++ - 如果未指定返回类型，递归 lambda 将无法编译

java - 如何将 double 值设置为 "non-value"

java - Android 9.0 设备上的 NumberFormatException，无法找到问题原因

algorithm - 如何生成最多有 k 个的 n 位格雷码？

©2024 IT工具网  联系我们