Palaisipan na may mga bracket (Level 3, Lecture 4)

May ganoong gawain, naniniwala ako, na nagdulot ng iba't ibang emosyon sa maraming JavaRush cadets. Noong Setyembre, nang simulan ko ang kurso, ang gawain ay nabuo tulad ng sumusunod: Sa expression na 1+2*3+4*5+6*7+8*9+10, ilagay ang dalawang pares ng panaklong upang ang halaga ng ang expression ay nagiging katumbas ng 537 Ngayon, sa pagbabalik sa solusyon, natuklasan ko na ang mga salita ay nabago, kinakailangan na maglagay ng dalawang pares ng mga bracket sa expression na 2*3+4*5+6*7 upang ang halaga ay maging katumbas ng 382. Ang ang bagong kondisyon, siyempre, ay mas simple kaysa sa nauna, dahil ang bilang ng mga posibleng opsyon ay nabawasan ng humigit-kumulang isang order ng magnitude. Ngunit ang natitirang 85 ay sapat na upang gumugol ng isang oras o dalawa sa manu-manong paghahanap. Malinaw, ang gawain ay hindi direktang nauugnay sa Java programming. Kaya lang hindi ko na-solve. Ang ganitong mga problema ay walang anumang analytical na solusyon batay sa pangangatwiran o mga katangian ng mga numero, tanging malupit na puwersa, katulad ng isang mapurol na paghahanap ng lahat ng posibleng mga pagpipilian. Sa kabilang banda, hindi gaanong halata na sa tulong ng programming na ang mga problema ng ganitong uri ay malulutas. Kaya naman bumalik ako. Nasanay na lang ako sa IDE, at ang mga problema ng kurso sa antas 8 ay sumabog sa aking isipan at hindi ko naisip na gumugol ng isang gabi o dalawa sa paglutas ng mga ito. Nasa ibaba kung paano mo malulutas ang problemang ito gamit ang Java. Ginamit ko ang lumang kondisyon bilang batayan para sa halimbawa. Una sa lahat, kailangan namin ng isang paraan upang makalkula ang halaga ng isang expression na nakasulat bilang isang string. Hindi namin mahanap ang ganoong paraan sa karaniwang mga library ng Java. Na-google ko ito: http://www.cyberforum.ru/java-j2se/thread283139.html ay angkop para sa aming mga layunin. Ang algorithm ay batay sa reverse Polish notation at gumagana para sa wastong mga string na naglalaman ng apat na arithmetic operations at parentheses. Lumikha ng isang bagong proyekto kasama ang klase ng PPN, kopyahin at i-paste ang code mula sa link sa isang file. Maaaring malutas ang problema sa pangunahing() na pamamaraan ng klase ng PPN. Pero hindi naman kailangan. Ang ideolohiya ng Java ay batay sa paghahati ng isang problema sa maliliit na subtask, na ang bawat isa ay ipinatupad sa sarili nitong klase at pamamaraan. Ang isang mahusay na diskarte ay upang malutas ang problema sa ibang klase, na naka-save sa isang hiwalay na file. Samakatuwid, lumikha ng isa pang klase kung saan isusulat mo ang algorithm para sa pag-enumerate ng mga bracket. Upang kalkulahin ang halaga ng isang string, kailangan mong tawagan ang eval() na paraan ng klase ng PPN: Halimbawa, tulad nito

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

o kaya

int result = PPN.eval(s2);

Tingnan natin ang linya 1+2*3+4*5+6*7+8*9+10 at tanungin ang ating sarili kung gaano karaming mga paraan ang maaari nating ilagay ang panimulang panaklong? Maaari itong ilagay sa sampung paraan. Kung binibilangan mo ang mga character ng isang string na nagsisimula sa zero, ang pambungad na bracket ay maaaring ilagay sa mga posisyong {0,2,4,6,8,10,12,14,16,18}. Ang paglalagay ng panaklong, halimbawa, sa ikaanim na posisyon ay nangangahulugan na kailangan mong kunin ang lahat ng mga character mula zero hanggang limang kasama, pagkatapos ay maglagay ng panaklong, pagkatapos ay kunin ang lahat ng mga character mula sa ikaanim hanggang sa dulo ng linya: Katulad nito, maaaring ilagay ang pansarang panaklong sa mga posisyon {1,3,5,7,9,11,13,15,17,20}. Ang huling dalawang numero ay sumisira sa buong raspberry, lahat ng iba pang mga posisyon ay naiiba sa bawat isa ng dalawa, at 17 at 20 ng tatlo. Samakatuwid, hindi posibleng magdeklara ng variable na naglalaman ng numero ng posisyon ng closing bracket at dagdagan ang halaga nito ng dalawa sa bawat susunod na hakbang. Mag-iimbak kami ng mga halaga ng posisyon sa mga 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};

At tataas namin ang variable ng index ng isa sa bawat pag-ulit ng loop na responsable para sa pag-enumerate ng mga opsyon. Sa kabuuan, kailangan ang dalawang pambungad at dalawang panaklong panaklong, ayon sa pagkakabanggit, apat na variable ng index ang kinakailangan:

int indLeft1, indLeft2, indRight1, indRight2;

Ang mga panaklong sa isang expression ay maaaring ilagay sa dalawang paraan:

(  )  (  )
(  (  )   )

Para sa bawat paraan kailangan mong isulat ang iyong sariling algorithm; isaalang-alang ang algorithm para sa unang paraan ng pag-aayos ng mga bracket. Ang aktwal na enumeration ng mga opsyon ay kinakatawan ng nested for loops:

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

Sa simula ng programa, sinisimulan namin ang string variable gamit ang orihinal na string na walang panaklong:

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

Sa katawan ng panloob na loop ay bumubuo kami ng isang linya na may mga bracket:

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

Bigyang-pansin ang kakaibang paraan ng substring() ng klase ng String. Pinili ang isang substring, ang bilang ng unang character na katumbas ng unang parameter, at ang bilang ng huli ay katumbas ng pangalawang parameter na minus one . tingnan ang https://docs.oracle.com/javase/10/docs/api/java/lang/String.html#substring(int,int) , may mga halimbawang ibinigay para mabawasan ang mga hindi pagkakaunawaan. Pagkatapos bumuo ng isang string na may mga bracket, kinakalkula namin ang halaga at ihambing ito sa kinakailangang isa:

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

Ang bloke para sa nested arrangement ng mga bracket ay nakasulat sa katulad na paraan. Ang tanging bagay na gusto kong bigyang pansin ay kapag ang mga bracket ay nakapugad, ang pagbubukas o pagsasara ng mga bracket ay maaaring nasa parehong posisyon, halimbawa.

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

o

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

Actually, yun lang. Pagkatapos ng paglunsad, ang isang wastong nakasulat na programa ay gumagawa ng isang sagot: 1+2*(3+4*(5+6*7)+8*9)+10