ปริศนาพร้อมวงเล็บ (ระดับ 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 ทำให้ฉันทึ่ง และฉันไม่รังเกียจที่จะใช้เวลาหนึ่งหรือสองช่วงเย็นในการแก้ปัญหาเหล่านั้น ด้านล่างนี้คือวิธีที่คุณสามารถแก้ไขปัญหานี้โดยใช้ Java ฉันใช้เงื่อนไขเก่าเป็นพื้นฐานสำหรับตัวอย่าง ก่อนอื่น เราต้องการวิธีคำนวณค่าของนิพจน์ที่เขียนเป็นสตริง เราไม่พบวิธีการดังกล่าวในไลบรารี Java มาตรฐาน ฉันค้นหาสิ่งนี้: http://www.cyberforum.ru/java-j2se/thread283139.htmlค่อนข้างเหมาะสมกับวัตถุประสงค์ของเรา อัลกอริทึมจะขึ้นอยู่กับสัญกรณ์โปแลนด์ย้อนกลับ และใช้ได้กับสตริงที่ถูกต้องซึ่งมีการดำเนินการทางคณิตศาสตร์และวงเล็บสี่รายการ สร้างโปรเจ็กต์ใหม่โดยมีคลาส PPN อยู่ในนั้น คัดลอกและวางโค้ดจากลิงก์ลงในไฟล์ ปัญหาสามารถแก้ไขได้ในเมธอด main() ของคลาส PPN แต่ก็ไม่จำเป็น อุดมการณ์ของ Java มีพื้นฐานมาจากการแบ่งปัญหาออกเป็นงานย่อยเล็กๆ ซึ่งแต่ละงานจะถูกนำไปใช้ในระดับและวิธีการของตัวเอง แนวทางที่ดีคือการแก้ปัญหาในคลาสอื่นโดยบันทึกไว้ในไฟล์แยกต่างหาก ดังนั้นให้สร้างคลาสอื่นที่คุณจะเขียนอัลกอริทึมสำหรับการแจกแจงวงเล็บ ในการคำนวณค่าของสตริง คุณต้องเรียกใช้เมธอด 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} ได้ ตัวอย่างเช่น การวางวงเล็บในตำแหน่งที่ 6 หมายความว่าคุณต้องนำอักขระทั้งหมดตั้งแต่ 0 ถึง 5 ตัว จากนั้นจึงใส่วงเล็บ จากนั้นนำอักขระทั้งหมดจากตำแหน่งที่ 6 ไปจนสุดบรรทัด: ในทำนองเดียวกัน วงเล็บปิดสามารถวางไว้ที่ตำแหน่ง {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 (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