Puzzle con parentesi (Livello 3, Lezione 4)

Credo che esista un compito del genere che ha suscitato varie emozioni tra molti cadetti JavaRush. A settembre, quando ho iniziato il corso, il compito era così formulato: Nell'espressione 1+2*3+4*5+6*7+8*9+10, inserire due coppie di parentesi in modo che il valore di l'espressione diventa uguale a 537 Ora, tornato alla soluzione, ho scoperto che la dicitura è stata cambiata, è necessario inserire due coppie di parentesi nell'espressione 2*3+4*5+6*7 in modo che il valore diventi uguale a 382. la nuova condizione, ovviamente, è più semplice della precedente, perché il numero di opzioni possibili è diminuito di circa un ordine di grandezza. Ma i restanti 85 sono sufficienti per dedicare un'ora o due alla ricerca manuale. Ovviamente l'attività non è direttamente correlata alla programmazione Java. Ecco perché non l'ho risolto. Tali problemi non hanno soluzioni analitiche basate sul ragionamento o sulle proprietà dei numeri, ma solo la forza bruta, cioè una ricerca schietta di tutte le opzioni possibili. D'altra parte, non è meno ovvio che è con l'aiuto della programmazione che problemi di questo tipo vengono risolti. Ecco perché sono tornato. Mi sono appena abituato all'IDE e i problemi del corso al livello 8 mi hanno lasciato a bocca aperta e non mi dispiaceva passare una o due sere a risolverli. Di seguito è riportato come risolvere questo problema utilizzando Java. Ho usato la vecchia condizione come base per l'esempio. Prima di tutto, abbiamo bisogno di un modo per calcolare il valore di un'espressione scritta come stringa. Non siamo riusciti a trovare un metodo del genere nelle librerie Java standard. Ho cercato su Google questo: http://www.cyberforum.ru/java-j2se/thread283139.html è abbastanza adatto ai nostri scopi. L'algoritmo si basa sulla notazione polacca inversa e funziona con stringhe valide contenenti quattro operazioni aritmetiche e parentesi. Crea un nuovo progetto con la classe PPN al suo interno, copia e incolla il codice dal collegamento in un file. Il problema può essere risolto nel metodo main() della classe PPN. Ma non è necessario. L'ideologia Java si basa sulla divisione di un problema in piccole sottoattività, ciascuna delle quali è implementata nella propria classe e metodo. Un buon approccio sarebbe risolvere il problema in un'altra classe, salvata in un file separato. Pertanto, crea un'altra classe in cui scriverai l'algoritmo per l'enumerazione delle parentesi. Per calcolare il valore di una stringa, è necessario chiamare il metodo eval() della classe PPN: Ad esempio, in questo modo

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

o così

int result = PPN.eval(s2);

Diamo un'occhiata più da vicino alla riga 1+2*3+4*5+6*7+8*9+10 e chiediamoci in quanti modi possiamo inserire una parentesi di apertura? Può essere posizionato in dieci modi. Se si numerano i caratteri di una stringa partendo da zero, la parentesi aperta può essere posizionata nelle posizioni {0,2,4,6,8,10,12,14,16,18}. Posizionare una parentesi, ad esempio, nella sesta posizione significa che è necessario prendere tutti i caratteri da zero a cinque compresi, quindi inserire una parentesi, quindi prendere tutti i caratteri dal sesto alla fine della riga: Allo stesso modo, la parentesi di chiusura può essere posizionata nelle posizioni {1,3,5,7,9,11,13,15,17,20}. Gli ultimi due numeri rovinano l'intero pernacchio, tutte le altre posizioni differiscono l'una dall'altra di due e 17 e 20 di tre. Pertanto non sarà possibile dichiarare semplicemente una variabile che contenga il numero di posizione della parentesi di chiusura e incrementarne il valore di due ad ogni passo successivo. Memorizzeremo i valori di posizione negli 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};

E aumenteremo la variabile indice di uno ad ogni iterazione del ciclo responsabile dell'enumerazione delle opzioni. In totale, sono necessarie rispettivamente due parentesi di apertura e due di chiusura, quattro variabili indice:

int indLeft1, indLeft2, indRight1, indRight2;

Le parentesi in un'espressione possono essere posizionate in due modi:

(  )  (  )
(  (  )   )

Per ogni metodo devi scrivere il tuo algoritmo; considera l'algoritmo per il primo metodo di disposizione delle parentesi. L'effettiva enumerazione delle opzioni è rappresentata da cicli for nidificati:

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

All'inizio del programma inizializziamo la variabile stringa con la stringa originale senza parentesi:

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

Nel corpo del ciclo interno formiamo una linea con parentesi:

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

Presta attenzione alla particolarità del metodo substring() della classe String. Viene selezionata una sottostringa, il cui numero del primo carattere è uguale al primo parametro e il numero dell'ultimo è uguale al secondo parametro meno uno . vedere https://docs.oracle.com/javase/10/docs/api/java/lang/String.html#substring(int,int) , ci sono anche esempi forniti per ridurre le incomprensioni. Dopo aver formato una stringa tra parentesi, calcoliamo il valore e confrontiamolo con quello richiesto:

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

Il blocco per la disposizione annidata delle parentesi è scritto in modo simile. L'unica cosa su cui voglio attirare l'attenzione è che quando le parentesi sono annidate, le parentesi di apertura o di chiusura possono trovarsi nella stessa posizione, ad esempio

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

O

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

In realtà, questo è tutto. Dopo il lancio, un programma scritto correttamente produce un'unica risposta: 1+2*(3+4*(5+6*7)+8*9)+10