All geek questions in one place

Get the minimum and maximum value of an expression using parentheses

I have a single line expression without parentheses, for example 1+5*6-3. We can use all operators ( +, -, *, /). What do i need to know? The maximum and minimum value of an expression when we can use parentheses.

Examples

1)
Input: 1+5*6-3
Output:33 16

Explanation: 33 = (((1+5)*6)-3)|16 = (1+(5*(6-3))

2)
Input: 15*5-12-9
Output:72 -240

3)
Input: 3*10*16-14-11*2
Output:954 -600

4)
Input: 8-5*18+5-13+0*2+14-6*6+1
Output:7233 -13482

5)
Input: 6+5-15*18+14-3-5-3-2-2*8-14+12
Output:11081 -4935

6)
Input: 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
Output: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;
}
+4
1

, . , . , , ,

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

- ( , ) . min/max / min 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. , . , ...

EDIT: , , , . , , , . , : (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 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)
+2

Source: https://habr.com/ru/post/1613851/

More articles:


All Articles