Головоломка зі дужками (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