带括号的拼图（第 3 级，第 4 讲）

我相信有这样一个任务引起了许多 JavaRush 学员的不同情绪。9月份，当我开始课程时，任务是这样表述的：在表达式1+2*3+4*5+6*7+8*9+10中，放置两对括号，使得表达式变为等于 537 现在，回到解决方案，我发现措辞已更改；需要在表达式 2*3+4*5+6*7 中放置两对括号，以便该值等于 382。当然，新条件比前一个条件简单，因为 可能的选项数量减少了大约一个数量级。但剩下的85个已经足够手动搜索一两个小时了。显然，该任务与 Java 编程没有直接关系。这就是为什么我没有解决它。此类问题没有任何基于推理或数字属性的分析解决方案，只有蛮力，即对所有可能选项的生硬搜索。另一方面，同样明显的是，借助编程可以解决此类问题。这就是我回来的原因。我刚刚习惯了 IDE，第 8 级课程中的问题让我大吃一惊，我不介意花一两个晚上来解决它们。下面介绍如何使用 Java 解决此问题。我使用旧条件作为示例的基础。首先，我们需要一种方法来计算以字符串形式编写的表达式的值。我们在标准Java库中找不到这样的方法。我用谷歌搜索了这个： http: //www.cyberforum.ru/java-j2se/thread283139.html非常适合我们的目的。该算法基于逆波兰表示法，适用于包含四个算术运算和括号的有效字符串。创建一个包含 PPN 类的新项目，将链接中的代码复制并粘贴到文件中。该问题可以在PPN类的main()方法中解决。但这没有必要。Java 思想基于将问题划分为小的子任务，每个子任务都在自己的类和方法中实现。一个好的方法是在另一个类中解决问题，并保存在单独的文件中。因此，创建另一个类，您将在其中编写枚举括号的算法。要计算字符串的值，需要调用PPN类的eval()方法：例如，像这样

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}。最后两个数字破坏了整个树莓派，所有其他位置彼此相差 2，17 和 20 相差 3。因此，不可能简单地声明一个包含右括号位置编号的变量，并在下一步中将其值增加 2。我们将位置值存储在数组中：

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

请注意 String 类的 substring() 方法的特殊性。选择一个子字符串，其第一个字符的编号等于第一个参数，最后一个字符的编号等于第二个参数减一。请参阅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