生成添加到目标的所有数学表达式组合（Java家庭作业/面试）

algorithm math java expression

2022-09-03 06:43:38

我试图解决下面的编码挑战问题，但无法在1小时内完成。我对算法的工作原理有一个想法，但我不太确定如何最好地实现它。我在下面有我的代码和问题。

pi 的前 12 位数字314159265358。我们可以将这些数字转换为计算结果为 27182（e 的前 5 位数字）的表达式，如下所示：
3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8 = 27182
或
3 + 1 - 415 * 92 + 65358 = 27182
请注意，输入数字的顺序不会更改。只需插入运算符（+,-,/ 或 *）即可创建表达式。

编写一个函数来获取数字和目标的列表，并返回将这些数字形成为计算目标的表达式的所有方式

例如：
f（“314159265358”， 27182）应打印：
3 + 1 - 415 * 92 + 65358 = 27182
3 * 1 + 4 * 159 + 26535 + 8 = 27182
3 / 1 + 4 * 159 + 26535 + 8 = 27182
3 * 14 * 15 + 9 + 26535 + 8 = 27182
3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8 = 27182

这个问题很困难，因为你可以有任何数字组合，而且你不会一次考虑一个数字。我不确定如何为该步骤进行组合和递归。请注意，解决方案中未提供括号，但保留了操作顺序。

我的目标是从说说开始

{"3"}
then
{"31", "3+1", "3-1", "3*1" "3/1"}
then
{"314", "31+4", "3+1+4", "3-1-4", "31/4", "31*4", "31-4"} etc.

然后每次查看列表中的每个值，看看它是否是目标值。如果是，请将该字符串添加到结果列表。

这是我的代码

public static List<String> combinations(String nums, int target)
    {

        List<String> tempResultList = new ArrayList<String>();
        List<String> realResultList = new ArrayList<String>();
        String originalNum = Character.toString(nums.charAt(0));


        for (int i = 0; i < nums.length(); i++)
        {
            if (i > 0)
            {
                originalNum += nums.charAt(i); //start off with a new number to decompose
            }
            tempResultList.add(originalNum);
            char[] originalNumCharArray = originalNum.toCharArray();
            for (int j = 0; j < originalNumCharArray.length; j++)
            {
                //go through every character to find the combinations?
                // maybe recursion here instead of iterative would be easier...
            }
            for (String s : tempResultList)
            {
                //try to evaluate
                int temp = 0;
               if (s.contains("*") || s.contains("/") || s.contains("+") || s.contains("-"))
               {
                  //evaluate expression
               } else {
                   //just a number
               }
                if (temp == target)
                {
                    realResultList.add(s);
                }

            }
         tempResultList.clear();
        }
        return realResultList;
    }

有人可以帮助解决这个问题吗？寻找带有编码的答案，因为我需要帮助来产生可能性

答案 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

并获得答案：

接下来，您需要创建一个树结构。您的第一和第二级已完成。

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 个表达式叶，直到您使用了所有输入数字。

使用完所有输入数字后，请检查每个叶方程以查看它是否等于该值。