Получить минимальное и максимальное значение выражения с помощью скобок

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 a получить плохие результаты. Зачем? Может быть, вы увидите, что я сделал неправильно. Вот мой код:

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 ... 

потому, что некоторые минимальные операнды в сочетании с некоторыми операндами (я подозреваю, вычитать и делить) дают больший результат и наоборот.Поэтому все комбинации мин/макс влево/вправо должны быть проверены на наличие новых мин и нового максимального значения:

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]; 

Код работает очень хорошо без результатаУдаление вообще. Но это конечное условие рекурсии делает его действительно быстрым, не теряя результатов. Я был бы рад услышать, как это работает ...

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'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 + ")"; 
    } 
} 

, который показывает (последние два, чтобы увидеть, является ли это делить на ноль-SAFE):

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)