Rompecabezas con paréntesis (Nivel 3, Conferencia 4)

Creo que existe una tarea que causó varias emociones entre muchos cadetes de JavaRush. En septiembre, cuando comencé el curso, la tarea estaba formulada de la siguiente manera: En la expresión 1+2*3+4*5+6*7+8*9+10, coloque dos pares de paréntesis para que el valor del la expresión se vuelve igual a 537 Ahora, volviendo a la solución, descubrí que la redacción ha sido cambiada, es necesario colocar dos pares de corchetes en la expresión 2*3+4*5+6*7 para que el valor sea igual a 382. La nueva condición, por supuesto, es más sencilla que la anterior, porque el número de opciones posibles ha disminuido en aproximadamente un orden de magnitud. Pero los 85 restantes son suficientes para dedicar una o dos horas a la búsqueda manual. Obviamente, la tarea no está directamente relacionada con la programación Java. Por eso no lo resolví. Estos problemas no tienen soluciones analíticas basadas en el razonamiento o las propiedades de los números, sólo fuerza bruta, es decir, una búsqueda contundente de todas las opciones posibles. Por otro lado, no es menos obvio que es con la ayuda de la programación como se resuelven problemas de este tipo. Por eso volví. Me acabo de acostumbrar al IDE y los problemas del curso del nivel 8 me dejaron boquiabierto y no me importó dedicar una o dos noches a resolverlos. A continuación se muestra cómo puede resolver este problema utilizando Java. Utilicé la antigua condición como base para el ejemplo. En primer lugar, necesitamos una forma de calcular el valor de una expresión escrita como una cadena. No pudimos encontrar un método de este tipo en las bibliotecas estándar de Java. Busqué en Google esto: http://www.cyberforum.ru/java-j2se/thread283139.html es bastante adecuado para nuestros propósitos. El algoritmo se basa en la notación polaca inversa y funciona con cadenas válidas que contienen cuatro operaciones aritméticas y paréntesis. Cree un nuevo proyecto con la clase PPN, copie y pegue el código del enlace en un archivo. El problema se puede resolver en el método main() de la clase PPN. Pero no es necesario. La ideología de Java se basa en dividir un problema en pequeñas subtareas, cada una de las cuales se implementa en su propia clase y método. Un buen enfoque sería resolver el problema en otra clase, guardada en un archivo separado. Por lo tanto, cree otra clase en la que escribirá el algoritmo para enumerar corchetes. Para calcular el valor de una cadena, necesita llamar al método eval() de la clase PPN: por ejemplo, así

System.out.println(PPN.eval(“2*3+4”));

más o menos

int result = PPN.eval(s2);

Echemos un vistazo de cerca a la línea 1+2*3+4*5+6*7+8*9+10 y preguntémonos de cuántas maneras podemos poner un paréntesis de apertura. Se puede colocar de diez maneras. Si numera los caracteres de una cadena comenzando desde cero, entonces el corchete de apertura se puede colocar en las posiciones {0,2,4,6,8,10,12,14,16,18}. Colocar un paréntesis, por ejemplo, en la sexta posición significa que debe tomar todos los caracteres del cero al cinco inclusive, luego poner un paréntesis y luego tomar todos los caracteres desde el sexto hasta el final de la línea: De manera similar, el paréntesis de cierre se puede colocar en las posiciones {1,3,5,7,9,11,13,15,17,20}. Los dos últimos números estropean toda la frambuesa, todas las demás posiciones se diferencian entre sí en dos, y 17 y 20 en tres. Por lo tanto, no será posible simplemente declarar una variable que contenga el número de posición del corchete de cierre y aumentar su valor en dos en cada paso siguiente. Almacenaremos los valores de posición en matrices:

int[] left = {0,2,4,6,8,10,12,14,16,18};

int[] right = {1,3,5,7,9,11,13,15,17,20};

Y aumentaremos la variable de índice en uno en cada iteración del ciclo responsable de enumerar las opciones. En total, se necesitan dos paréntesis de apertura y dos de cierre, respectivamente, se requieren cuatro variables de índice:

int indLeft1, indLeft2, indRight1, indRight2;

Los paréntesis en una expresión se pueden colocar de dos maneras:

(  )  (  )
(  (  )   )

Para cada método necesita escribir su propio algoritmo; considere el algoritmo para el primer método de disposición de paréntesis. La enumeración real de opciones está representada por bucles for anidados:

for (int indLeft1=0;indLeft1<10;indLeft1++)
   for(int indRight1=indLeft1+1;indRight1<10;indRight1++)
      for (int indLeft2=indRight1+1;indLeft2<10;indLeft2++)
         for (int indRight2=indLeft2+1;indRight2<10;indRight2++)

Al comienzo del programa, inicializamos la variable de cadena con la cadena original sin paréntesis:

String s = "1+2*3+4*5+6*7+8*9+10";

En el cuerpo del bucle interior formamos una línea entre paréntesis:

String s2 = s.substring(0, left[indLeft1]) + "(" +
		 s.substring(left[indLeft1], right[indRight1]) + ")" +
		 s.substring(right[indRight1],left[indLeft2]) + "(" +
		 s.substring(left[indLeft2], right[indRight2]) + ")" +
		 s.substring(right[indRight2], s.length());

Preste atención a la peculiaridad del método substring() de la clase String. Se selecciona una subcadena, cuyo número del primer carácter es igual al primer parámetro y el número del último es igual al segundo parámetro menos uno . consulte https://docs.oracle.com/javase/10/docs/api/java/lang/String.html#substring(int,int) , incluso se dan ejemplos para reducir malentendidos. Después de formar una cadena entre paréntesis, calculamos el valor y lo comparamos con el requerido:

int result = PPN.eval(s2);
if (result == 537)
          System.out.println(s2);

El bloque para la disposición anidada de corchetes está escrito de forma similar. Lo único que quiero llamar la atención es que cuando los corchetes están anidados, los corchetes de apertura o cierre pueden estar en la misma posición, por ejemplo.

1+((2*3+4*5+6)*7+8*9+10)

o

(1+2*(3+4*5+6*7+8))*9+10

En realidad, eso es todo. Después del lanzamiento, un programa escrito correctamente produce una única respuesta: 1+2*(3+4*(5+6*7)+8*9)+10