Quebra-cabeça com colchetes (Nível 3, Aula 4)

Acredito que essa tarefa tenha causado várias emoções entre muitos cadetes do JavaRush. Em setembro, quando iniciei o curso, a tarefa estava formulada da seguinte forma: Na expressão 1+2*3+4*5+6*7+8*9+10, coloque dois pares de parênteses para que o valor do expressão torna-se igual a 537 Agora, voltando à solução, descobri que a redação foi alterada, é necessário colocar dois pares de colchetes na expressão 2*3+4*5+6*7 para que o valor fique igual a 382. O a nova condição, é claro, é mais simples que a anterior, porque o número de opções possíveis diminuiu aproximadamente uma ordem de grandeza. Mas os 85 restantes são suficientes para gastar uma ou duas horas em busca manual. Obviamente, a tarefa não está diretamente relacionada à programação Java. Por isso não resolvi. Tais problemas não têm soluções analíticas baseadas no raciocínio ou nas propriedades dos números, apenas força bruta, nomeadamente uma busca contundente de todas as opções possíveis. Por outro lado, não é menos óbvio que é com a ajuda da programação que problemas deste tipo se resolvem. Foi por isso que voltei. Acabei de me acostumar com o IDE, e os problemas do curso no nível 8 me surpreenderam e não me importei de passar uma ou duas noites resolvendo-os. Abaixo está como você pode resolver esse problema usando Java. Usei a condição antiga como base para o exemplo. Em primeiro lugar, precisamos de uma forma de calcular o valor de uma expressão escrita como uma string. Não conseguimos encontrar tal método nas bibliotecas Java padrão. Pesquisei no Google: http://www.cyberforum.ru/java-j2se/thread283139.html é bastante adequado para nossos propósitos. O algoritmo é baseado na notação polonesa reversa e funciona para strings válidas contendo quatro operações aritméticas e parênteses. Crie um novo projeto com a classe PPN, copie e cole o código do link em um arquivo. O problema pode ser resolvido no método main() da classe PPN. Mas não é necessário. A ideologia Java baseia-se na divisão de um problema em pequenas subtarefas, cada uma delas implementada em sua própria classe e método. Uma boa abordagem seria resolver o problema em outra classe, salva em um arquivo separado. Portanto, crie outra classe na qual você escreverá o algoritmo para enumerar colchetes. Para calcular o valor de uma string, você precisa chamar o método eval() da classe PPN: Por exemplo, assim

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

ou então

int result = PPN.eval(s2);

Vamos dar uma olhada na reta 1+2*3+4*5+6*7+8*9+10 e nos perguntar de quantas maneiras podemos colocar um parêntese de abertura? Pode ser colocado de dez maneiras. Se você numerar os caracteres de uma string começando em zero, o colchete de abertura poderá ser colocado nas posições {0,2,4,6,8,10,12,14,16,18}. Colocar um parêntese, por exemplo, na sexta posição significa que você precisa pegar todos os caracteres de zero a cinco inclusive, depois colocar um parêntese e depois pegar todos os caracteres do sexto até o final da linha: Da mesma forma, o parêntese de fechamento pode ser colocado nas posições {1,3,5,7,9,11,13,15,17,20}. Os dois últimos números estragam toda a framboesa, todas as outras posições diferem entre si em dois e 17 e 20 em três. Portanto, não será possível simplesmente declarar uma variável que contenha o número da posição do colchete de fechamento e aumentar seu valor em dois a cada passo seguinte. Armazenaremos valores de posição em arrays:

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 aumentaremos a variável de índice em um a cada iteração do loop responsável por enumerar as opções. No total, são necessários dois parênteses de abertura e dois de fechamento, respectivamente, são necessárias quatro variáveis ​​de índice:

int indLeft1, indLeft2, indRight1, indRight2;

Os parênteses em uma expressão podem ser colocados de duas maneiras:

(  )  (  )
(  (  )   )

Para cada método você precisa escrever seu próprio algoritmo; considere o algoritmo do primeiro método de organização de colchetes. A enumeração real de opções é representada por loops for aninhados:

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

No início do programa, inicializamos a variável string com a string original sem parênteses:

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

No corpo do loop interno formamos uma linha entre colchetes:

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

Preste atenção à peculiaridade do método substring() da classe String. Uma substring é selecionada, cujo número do primeiro caractere é igual ao primeiro parâmetro e o número do último é igual ao segundo parâmetro menos um . consulte https://docs.oracle.com/javase/10/docs/api/java/lang/String.html#substring(int,int) , há até exemplos dados para reduzir mal-entendidos. Após formar uma string entre colchetes, calculamos o valor e comparamos com o necessário:

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

O bloco para a disposição aninhada de colchetes é escrito de maneira semelhante. A única coisa que quero chamar a atenção é que quando os colchetes estão aninhados, os colchetes de abertura ou fechamento podem estar na mesma posição, por exemplo

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

ou

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

Na verdade, isso é tudo. Após o lançamento, um programa escrito corretamente produz uma única resposta: 1+2*(3+4*(5+6*7)+8*9)+10