Puzzle with brackets (Level 3, Lecture 4)

There is such a task, I believe, that caused various emotions among many JavaRush cadets. In September, when I started the course, the task was formulated as follows: In the expression 1+2*3+4*5+6*7+8*9+10, place two pairs of parentheses so that the value of the expression becomes equal to 537 Now, having returned to the solution, I discovered that the wording has been changed; it is necessary to place two pairs of brackets in the expression 2*3+4*5+6*7 so that the value becomes equal to 382. The new condition, of course, is simpler than the previous one, because the number of possible options has decreased by approximately an order of magnitude. But the remaining 85 are quite enough to spend an hour or two on manual search. Obviously, the task is not directly related to Java programming. That's why I didn't solve it. Such problems do not have any analytical solutions based on reasoning or the properties of numbers, only brute force, namely a blunt search of all possible options. On the other hand, it is no less obvious that it is with the help of programming that problems of this type are solved. That's why I came back. I just got used to the IDE, and the problems of the course by level 8 blew my mind and I didn’t mind spending an evening or two on solving them. Below is how you can solve this problem using Java. I used the old condition as the basis for the example. First of all, we need a way to calculate the value of an expression written as a string. We could not find such a method in the standard Java libraries. I googled this: http://www.cyberforum.ru/java-j2se/thread283139.html is quite suitable for our purposes. The algorithm is based on reverse Polish notation and works for valid strings containing four arithmetic operations and parentheses. Create a new project with the PPN class in it, copy and paste the code from the link into a file. The problem can be solved in the main() method of the PPN class. But it's not necessary. The Java ideology is based on dividing a problem into small subtasks, each of which is implemented in its own class and method. A good approach would be to solve the problem in another class, saved in a separate file. Therefore, create another class in which you will write the algorithm for enumerating brackets. To calculate the value of a string, you need to call the eval() method of the PPN class: For example, like this

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

or so

int result = PPN.eval(s2);

Let's take a close look at the line 1+2*3+4*5+6*7+8*9+10 and ask ourselves how many ways can we put an opening parenthesis? It can be placed in ten ways. If you number the characters of a string starting from zero, then the opening bracket can be placed in positions {0,2,4,6,8,10,12,14,16,18}. Placing a parenthesis, for example, in the sixth position means that you need to take all characters from zero to five inclusive, then put a parenthesis, then take all characters from the sixth to the end of the line: Similarly, the closing parenthesis can be placed at positions {1,3,5,7,9,11,13,15,17,20}. The last two numbers spoil the whole raspberry, all other positions differ from each other by two, and 17 and 20 by three. Therefore, it will not be possible to simply declare a variable that contains the position number of the closing bracket and increase its value by two at each next step. We will store position values ​​in arrays:

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

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

And we will increase the index variable by one at each iteration of the loop responsible for enumerating options. In total, two opening and two closing parentheses are needed, respectively, four index variables are required:

int indLeft1, indLeft2, indRight1, indRight2;

Parentheses in an expression can be placed in two ways:

(  )  (  )
(  (  )   )

For each method you need to write your own algorithm; consider the algorithm for the first method of arranging brackets. The actual enumeration of options is represented by nested for loops:

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

At the beginning of the program, we initialize the string variable with the original string without parentheses:

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

In the body of the inner loop we form a line with brackets:

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

Pay attention to the peculiarity of the substring() method of the String class. A substring is selected, the number of the first character of which is equal to the first parameter, and the number of the last is equal to the second parameter minus one . see https://docs.oracle.com/javase/10/docs/api/java/lang/String.html#substring(int,int) , there are even examples given to reduce misunderstandings. After forming a string with brackets, we calculate the value and compare it with the required one:

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

The block for the nested arrangement of brackets is written in a similar way. The only thing I want to draw attention to is that when the brackets are nested, the opening or closing brackets can be in the same position, for example

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

or

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

Actually, that's all. After launch, a correctly written program produces a single answer: 1+2*(3+4*(5+6*7)+8*9)+10