Puzzle dengan tanda kurung (Level 3, Kuliah 4)

Saya yakin ada tugas seperti itu yang menimbulkan berbagai emosi di antara banyak taruna JavaRush. Pada bulan September, ketika saya memulai kursus, tugasnya dirumuskan sebagai berikut: Dalam ekspresi 1+2*3+4*5+6*7+8*9+10, tempatkan dua pasang tanda kurung sehingga nilai dari ekspresi menjadi sama dengan 537 Sekarang, setelah kembali ke solusi, saya menemukan bahwa kata-katanya telah diubah; perlu menempatkan dua pasang tanda kurung dalam ekspresi 2*3+4*5+6*7 sehingga nilainya menjadi sama dengan 382. kondisi baru tentunya lebih sederhana dari sebelumnya, karena jumlah pilihan yang mungkin telah berkurang kira-kira satu urutan besarnya. Namun 85 sisanya cukup untuk menghabiskan satu atau dua jam untuk pencarian manual. Jelasnya, tugas tersebut tidak berhubungan langsung dengan pemrograman Java. Itu sebabnya saya tidak menyelesaikannya. Permasalahan seperti ini tidak mempunyai penyelesaian analitis berdasarkan penalaran atau sifat-sifat bilangan, hanya kekerasan (brute force), yaitu pencarian secara tumpul terhadap semua kemungkinan pilihan. Di sisi lain, yang tidak kalah jelasnya adalah dengan bantuan pemrograman masalah-masalah jenis ini dapat diselesaikan. Itu sebabnya saya kembali. Saya baru saja terbiasa dengan IDE, dan masalah kursus pada level 8 mengejutkan saya dan saya tidak keberatan menghabiskan satu atau dua malam untuk menyelesaikannya. Di bawah ini adalah bagaimana Anda dapat mengatasi masalah ini menggunakan Java. Saya menggunakan kondisi lama sebagai dasar contoh. Pertama-tama, kita memerlukan cara untuk menghitung nilai ekspresi yang ditulis sebagai string. Kami tidak dapat menemukan metode seperti itu di perpustakaan Java standar. Saya mencari ini di Google: http://www.cyberforum.ru/java-j2se/thread283139.html cukup cocok untuk tujuan kita. Algoritme ini didasarkan pada notasi Polandia terbalik dan berfungsi untuk string valid yang berisi empat operasi aritmatika dan tanda kurung. Buat proyek baru dengan kelas PPN di dalamnya, salin dan tempel kode dari tautan ke dalam file. Masalahnya dapat diselesaikan dalam metode main() pada kelas PPN. Tapi itu tidak perlu. Ideologi Java didasarkan pada pembagian masalah menjadi sub-tugas kecil, yang masing-masing diimplementasikan dalam kelas dan metodenya sendiri. Pendekatan yang baik adalah menyelesaikan masalah di kelas lain, disimpan dalam file terpisah. Oleh karena itu, buatlah kelas lain di mana Anda akan menulis algoritma untuk menghitung tanda kurung. Untuk menghitung nilai string, Anda perlu memanggil metode eval() kelas PPN: Misalnya seperti ini

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

atau lebih

int result = PPN.eval(s2);

Mari kita lihat lebih dekat baris 1+2*3+4*5+6*7+8*9+10 dan tanyakan pada diri kita sendiri, berapa banyak cara untuk meletakkan tanda kurung buka? Itu dapat ditempatkan dalam sepuluh cara. Jika penomoran karakter suatu string dimulai dari nol, maka tanda kurung buka dapat ditempatkan pada posisi {0,2,4,6,8,10,12,14,16,18}. Menempatkan tanda kurung, misalnya, di posisi keenam berarti Anda harus mengambil semua karakter dari nol hingga lima inklusif, lalu meletakkan tanda kurung, lalu mengambil semua karakter dari keenam hingga akhir baris: Demikian pula tanda kurung penutup dapat ditempatkan pada posisi {1,3,5,7,9,11,13,15,17,20}. Dua angka terakhir merusak keseluruhan raspberry, semua posisi lainnya berbeda satu sama lain sebanyak dua, dan 17 dan 20 sebanyak tiga. Oleh karena itu, tidak mungkin mendeklarasikan variabel yang memuat nomor posisi kurung tutup dan menaikkan nilainya sebanyak dua pada setiap langkah berikutnya. Kami akan menyimpan nilai posisi dalam array:

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

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

Dan kami akan meningkatkan variabel indeks sebanyak satu pada setiap iterasi loop yang bertanggung jawab untuk menghitung opsi. Secara total diperlukan dua tanda kurung buka dan dua tanda kurung tutup, masing-masing diperlukan empat variabel indeks:

int indLeft1, indLeft2, indRight1, indRight2;

Tanda kurung dalam sebuah ekspresi dapat ditempatkan dengan dua cara:

(  )  (  )
(  (  )   )

Untuk setiap metode, Anda perlu menulis algoritme Anda sendiri; pertimbangkan algoritme untuk metode pertama dalam menyusun tanda kurung. Pencacahan opsi yang sebenarnya diwakili oleh loop for yang disarangkan:

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

Di awal program, kita menginisialisasi variabel string dengan string asli tanpa tanda kurung:

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

Di badan loop bagian dalam kami membentuk garis dengan tanda kurung:

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

Perhatikan kekhasan metode substring() kelas String. Substring dipilih, jumlah karakter pertama sama dengan parameter pertama, dan jumlah karakter terakhir sama dengan parameter kedua dikurangi satu . lihat https://docs.Oracle.com/javase/10/docs/api/java/lang/String.html#substring(int,int) , bahkan ada contoh yang diberikan untuk mengurangi kesalahpahaman. Setelah membentuk string dengan tanda kurung, kami menghitung nilainya dan membandingkannya dengan yang diperlukan:

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

Blok untuk susunan tanda kurung bersarang ditulis dengan cara yang sama. Satu-satunya hal yang ingin saya perhatikan adalah ketika tanda kurung dirangkai, tanda kurung buka atau tutup bisa berada pada posisi yang sama, misalnya

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

atau

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

Sebenarnya, itu saja. Setelah peluncuran, program yang ditulis dengan benar menghasilkan satu jawaban: 1+2*(3+4*(5+6*7)+8*9)+10