括號的拼圖（第 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