Создайте все комбинации математических выражений, которые добавляются к цели (домашнее задание/интервью Java)

Ответ 1

Я не считаю необходимым строить дерево, вы должны уметь рассчитывать, когда вы идете - вам просто нужно немного отложить добавления и вычитания, чтобы правильно учитывать приоритет:

static void check(double sum, double previous, String digits, double target, String expr) {
   if (digits.length() == 0) {
     if (sum + previous == target) {
       System.out.println(expr + " = " + target);
     }
   } else {
     for (int i = 1; i <= digits.length(); i++) {
       double current = Double.parseDouble(digits.substring(0, i));
       String remaining = digits.substring(i);
       check(sum + previous, current, remaining, target, expr + " + " + current);
       check(sum, previous * current, remaining, target, expr + " * " + current);
       check(sum, previous / current, remaining, target, expr + " / " + current);
       check(sum + previous, -current, remaining, target, expr + " - " + current);
     }
   }
 }

 static void f(String digits, double target) {
   for (int i = 1; i <= digits.length(); i++) {
     String current = digits.substring(0, i);
     check(0, Double.parseDouble(current), digits.substring(i), target, current);
   }
 } 

Ответ 2

Сначала вам нужен метод, в котором вы можете ввести выражение

3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8

и получите ответ:

27182

Затем вам нужно создать древовидную структуру. Ваш первый и второй уровни завершены.

3
31, 3 + 1, 3 - 1, 3 * 1, 3 / 1

На вашем третьем уровне не хватает нескольких выражений.

31 -> 314, 31 + 4, 31 - 4, 31 * 4, 31 / 4
3 + 1 -> 3 + 14, 3 + 1 + 4, 3 + 1 - 4, 3 + 1 * 4, 3 + 1 / 4
3 - 1 -> 3 - 14, 3 - 1 + 4, 3 - 1 - 4, 3 - 1 * 4, 3 - 1 / 4
3 * 1 -> 3 * 14, 3 * 1 + 4, 3 * 1 - 4, 3 * 1 * 4, 3 * 1 / 4
3 / 1 -> 3 / 14, 3 / 1 + 4, 3 / 1 - 4, 3 / 1 * 4, 3 / 1 / 4

Вы можете прекратить добавлять листья в ветвь дерева, когда деление дает не целое число.

Как вы можете видеть, количество листьев на каждом уровне вашего дерева будет расти быстрыми темпами.

Для каждого листа вам нужно добавить следующее значение, следующее добавленное значение, вычесть, умножить и разделить. В качестве окончательного примера здесь находятся 5 из четвертого уровня:

3 * 1 + 4 -> 3 * 1 + 41, 3 * 1 + 4 + 1, 3 * 1 + 4 - 1, 3 * 1 + 4 * 1,
    3 * 1 + 4 / 1

Ваш код должен генерировать 5 листьев выражений для каждого листа, пока вы не будете использовать все входные цифры.

Когда вы использовали все входные цифры, проверьте каждое уравнение листа, чтобы убедиться, что оно равно значению.

Ответ 3

Моя реализация Javascript:
Улучшит код, используя веб-исполнителя позже

// was not allowed to use eval , so this is my replacement for the eval function.
function evaluate(expr) {
  return new Function('return '+expr)();
 }
 function calc(expr,input,target) { 
   if (input.length==1) { 
    // I'm not allowed to use eval, so I will use my function evaluate
    //if (eval(expr+input)==target) console.log(expr+input+"="+target);
    if (evaluate(expr+input)==target) document.body.innerHTML+=expr+input+"="+target+"<br>";
   }
   else { 
     for(var i=1;i<=input.length;i++) {
      var left=input.substring(0,i);
      var right=input.substring(i);
      ['+','-','*','/'].forEach(function(oper) {
         calc(expr+left+oper,right,target);
      },this);
     }
   }
 };
 function f(input,total) {
  calc("",input,total);
 }