生成添加到目标的所有数学表达式组合（Java家庭作业/访谈）
我试图解决下面的问题以解决编码问题，但无法在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 combinations(String nums, int target) { List tempResultList = new ArrayList(); List realResultList = new ArrayList(); String originalNum = Character.toString(nums.charAt(0)); for (int i = 0; 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; }
有人可以帮助解决这个问题吗？ 寻找带有编码的答案，因为我需要帮助来产生可能性
我不认为有必要构建一个树，你应该能够随时计算 – 你只需要稍微延迟加法和减法，以便能够正确地考虑优先级：
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); } }
首先，您需要一个可以输入表达式的方法
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个表达式叶子，直到您使用了所有输入数字。
当您使用了所有输入数字时，请检查每个叶子方程式以查看它是否等于该值。
我的Javascript实现：
稍后将使用Web worker改进代码
// 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+"
"; } 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); }