Головоломка со скобками (3 уровень, 4 лекция)

Есть такая задача, полагаю, вызвавшая разнообразные эмоции у многих курсантов JavaRush. В сентябре, когда я начинал курс, задача формулировалась следующим образом: В выражении 1+2*3+4*5+6*7+8*9+10 расставить две пары скобок так, чтобы значение выражения стало равным 537 Сейчас, вернувшись к решению, обнаружил, что формулировка изменена, необходимо расставить две пары скобок в выражении 2*3+4*5+6*7 так, чтобы значение стало равным 382. Новое условие, конечно, проще предыдущего, т.к. количество возможных вариантов уменьшилось примерно на порядок. Но оставшихся 85 вполне хватит для того чтобы потратить на ручной перебор часок-другой. Очевидно, задача не имеет непосредственного отношения к программированию на Java. Поэтому я её и не стал решать. Такие задачи не имеют каких-либо аналитических решений основанных на рассуждениях или свойствах чисел, только перебор, именно тупой перебор в лоб всех возможных вариантов. С другой стороны, не менее очевидно, что именно с помощью программирования и решаются задачи такого вида. Поэтому и вернулся. Как раз освоился с IDE, а задачи курса к 8 уровню вынесли мозг и стало не жалко потратить вечерок-другой на решение. Ниже показано как можно решить эту задачу с помощью Javа. В основу примера взял старое условие. В первую очередь нужен способ вычислить значение выражения записанного в виде строки. В стандартных библиотеках Явы такого метода найти не удалось. Нагуглилось вот это: http://www.cyberforum.ru/java-j2se/thread283139.html вполне подойдет для наших целей. Алгоритм основан на обратной польской записи и работает для корректных строк содержащих четыре арифметических операции и круглые скобки. Создаете новый проект, в нем класс PPN, копипастите в файл код по ссылке. Задачу можно решать в методе main() класса PPN. Но не нужно. Идеология Явы строится на разделении проблемы на маленькие подзадачи, каждая из которых реализуется в своем классе и методе. Хорошим подходом будет решать задачу в другом классе, сохраненном в отдельном файле. Поэтому, создаете еще один класс, в котором запишете алгоритм перебора скобочек. Для вычисления значения строки нужно вызвать метод eval() класса PPN: Например, так

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

или так

int result = PPN.eval(s2);

Внимательно посмотрим на строку 1+2*3+4*5+6*7+8*9+10 и зададимся вопросом, каким количеством способов можно поставить открывающуюся скобку? Её можно поставить десятью способами. Если пронумеровать символы строки начиная с нуля, то открывающуюся скобку можно поставить в позициях {0,2,4,6,8,10,12,14,16,18}. Установка скобки, к примеру, в шестую позицию означает что нужно взять все символы с нулевого по пятый включительно, затем поставить скобку, затем взять все символы с шестого до конца строки: Аналогично, закрывающую скобку можно поставить в позициях {1,3,5,7,9,11,13,15,17,20}. Последние два числа портят всю малину, все остальные позиции отличаются друг от друга на два, а 17 и 20 на три. Поэтому не получится просто объявить переменную в которой записан номер позиции закрывающей скобки и при каждом очередном шаге увеличивать ее значение на два. Значения позиций будем хранить в массивах:

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

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

А увеличивать будем переменную-индекс, на единицу при каждой итерации цикла отвечающего за перебор вариантов. Всего нужны две открывающие и две закрывающие скобки, соответственно потребуется четыре переменных-индекса:

int indLeft1, indLeft2, indRight1, indRight2;

Скобки в выражении можно расставить двумя способами:

(  )  (  )
(  (  )   )

для каждого из способов нужно написать свой алгоритм, рассмотрим алгоритм для первого способа расположения скобок. Непосредственно перебор вариантов представляет собой вложенные циклы for:

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

В начале программы инициализируем строковую переменную исходной строкой без скобок:

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

В теле внутреннего цикла формируем строку со скобками:

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());

Обратите внимание на особенность метода substring() класса String. Выделяется подстрока, номер первого символа которой равен первому параметру, а номер последнего равен второму параметру минус единица. см. https://docs.oracle.com/javase/10/docs/api/java/lang/String.html#substring(int,int) , там даже примеры приведены для уменьшения недопонимания. После формирования строки со скобками, вычисляем значение и сравниваем с требуемым:

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

Аналогично пишется блок для вложенного расположения скобочек. Единственное на что хочу обратить внимание, при вложенном расположении скобочек, открывающие или закрывающие скобки могут находится в одной позиции, например

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

или

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

Собственно, все. После запуска корректно написанная программа выдает единственный ответ: 1+2*(3+4*(5+6*7)+8*9)+10