Câu đố có dấu ngoặc (Cấp độ 3, Bài giảng 4)

Tôi tin rằng có một nhiệm vụ như vậy đã gây ra nhiều cảm xúc khác nhau trong nhiều học viên JavaRush. Vào tháng 9, khi tôi bắt đầu khóa học, nhiệm vụ được đặt ra như sau: Trong biểu thức 1+2*3+4*5+6*7+8*9+10, đặt hai cặp dấu ngoặc đơn sao cho giá trị của biểu thức trở thành bằng 537 Bây giờ, khi quay lại giải pháp, tôi phát hiện ra rằng cách diễn đạt đã được thay đổi, cần đặt hai cặp dấu ngoặc trong biểu thức 2*3+4*5+6*7 để giá trị trở thành bằng 382. Tất nhiên, điều kiện mới đơn giản hơn điều kiện trước đó vì số lượng các lựa chọn có thể đã giảm đi khoảng một bậc độ lớn. Nhưng 85 còn lại là khá đủ để dành một hoặc hai giờ cho việc tìm kiếm thủ công. Rõ ràng, nhiệm vụ này không liên quan trực tiếp đến lập trình Java. Đó là lý do tại sao tôi không giải quyết nó. Những vấn đề như vậy không có bất kỳ giải pháp phân tích nào dựa trên lý luận hoặc tính chất của các con số, chỉ có sức mạnh vũ phu, cụ thể là tìm kiếm thẳng thừng tất cả các phương án có thể. Mặt khác, không kém phần hiển nhiên là với sự trợ giúp của lập trình, các vấn đề thuộc loại này sẽ được giải quyết. Đó là lý do tôi quay lại. Tôi mới làm quen với IDE và các vấn đề của khóa học ở cấp độ 8 đã làm tôi choáng váng và tôi không ngại dành một hoặc hai buổi tối để giải quyết chúng. Dưới đây là cách bạn có thể giải quyết vấn đề này bằng Java. Tôi đã sử dụng điều kiện cũ làm cơ sở cho ví dụ. Trước hết, chúng ta cần một cách để tính giá trị của một biểu thức được viết dưới dạng chuỗi. Chúng tôi không thể tìm thấy phương thức như vậy trong các thư viện Java tiêu chuẩn. Tôi đã tìm kiếm cái này trên Google: http://www.cyberforum.ru/java-j2se/thread283139.html khá phù hợp với mục đích của chúng tôi. Thuật toán dựa trên ký hiệu Ba Lan ngược và hoạt động với các chuỗi hợp lệ chứa bốn phép tính số học và dấu ngoặc đơn. Tạo một dự án mới với lớp PPN trong đó, sao chép và dán mã từ liên kết vào một tệp. Vấn đề có thể được giải quyết bằng phương thức main() của lớp PPN. Nhưng nó không cần thiết. Hệ tư tưởng Java dựa trên việc chia một vấn đề thành các nhiệm vụ nhỏ, mỗi nhiệm vụ được triển khai theo lớp và phương thức riêng. Một cách tiếp cận tốt là giải quyết vấn đề ở một lớp khác, được lưu trong một tệp riêng. Do đó, hãy tạo một lớp khác trong đó bạn sẽ viết thuật toán liệt kê các dấu ngoặc. Để tính giá trị của một chuỗi, bạn cần gọi phương thức eval() của lớp PPN: Ví dụ như thế này

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

hoặc là

int result = PPN.eval(s2);

Chúng ta hãy xem xét kỹ dòng 1+2*3+4*5+6*7+8*9+10 và tự hỏi có bao nhiêu cách chúng ta có thể đặt dấu ngoặc đơn mở đầu? Nó có thể được đặt theo mười cách. Nếu bạn đánh số các ký tự của chuỗi bắt đầu từ 0 thì dấu ngoặc mở có thể được đặt ở các vị trí {0,2,4,6,8,10,12,14,16,18}. Ví dụ, đặt dấu ngoặc đơn ở vị trí thứ sáu có nghĩa là bạn cần lấy tất cả các ký tự từ 0 đến 5, sau đó đặt dấu ngoặc đơn, sau đó lấy tất cả các ký tự từ thứ sáu đến cuối dòng: Tương tự, dấu ngoặc đơn đóng có thể được đặt ở vị trí {1,3,5,7,9,11,13,15,17,20}. Hai số cuối cùng làm hỏng toàn bộ quả mâm xôi, tất cả các vị trí khác cách nhau hai, và 17 và 20 bằng ba. Do đó, sẽ không thể chỉ khai báo một biến chứa số vị trí của dấu ngoặc đóng và tăng giá trị của nó lên hai ở mỗi bước tiếp theo. Chúng ta sẽ lưu trữ các giá trị vị trí trong mảng:

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

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

Và chúng tôi sẽ tăng biến chỉ mục lên một biến tại mỗi lần lặp của vòng lặp chịu trách nhiệm liệt kê các tùy chọn. Tổng cộng cần có hai dấu ngoặc đơn mở và hai dấu ngoặc đơn đóng, tương ứng cần có bốn biến chỉ số:

int indLeft1, indLeft2, indRight1, indRight2;

Dấu ngoặc đơn trong một biểu thức có thể được đặt theo hai cách:

(  )  (  )
(  (  )   )

Đối với mỗi phương pháp bạn cần viết thuật toán của riêng mình, xem xét thuật toán cho phương pháp sắp xếp dấu ngoặc đầu tiên. Việc liệt kê thực tế các tùy chọn được thể hiện bằng các vòng lặp for lồng nhau:

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

Khi bắt đầu chương trình, chúng ta khởi tạo biến chuỗi bằng chuỗi gốc không có dấu ngoặc đơn:

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

Trong phần thân của vòng lặp bên trong, chúng ta tạo thành một dòng có dấu ngoặc:

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

Hãy chú ý đến tính đặc thù của phương thức substring() của lớp String. Một chuỗi con được chọn, số ký tự đầu tiên bằng tham số đầu tiên và số ký tự cuối cùng bằng tham số thứ hai trừ đi một . xem https://docs.oracle.com/javase/10/docs/api/java/lang/String.html#substring(int,int) , thậm chí có những ví dụ được đưa ra để giảm bớt sự hiểu lầm. Sau khi tạo một chuỗi có dấu ngoặc, chúng ta tính giá trị và so sánh nó với chuỗi được yêu cầu:

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

Khối sắp xếp các dấu ngoặc lồng nhau được viết theo cách tương tự. Điều duy nhất tôi muốn chú ý là khi các dấu ngoặc lồng nhau thì dấu ngoặc mở hoặc đóng có thể ở cùng một vị trí chẳng hạn.

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

hoặc

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

Trên thực tế, đó là tất cả. Sau khi khởi chạy, một chương trình được viết đúng sẽ tạo ra một câu trả lời duy nhất: 1+2*(3+4*(5+6*7)+8*9)+10