我正在为 Java 构建一个数学游戏，但根据我的作业细节，我一直停留在这部分。规则很简单:您必须只使用每个数字一次，并且只能使用从用户那里读取的 4 个数字来找到一个等式来获得 24。

例如，对于数字 4,7,8,8，可能的解是:(7-(8/8))*4=24。

大多数 4 位数字组可用于多个得出 24 的方程式。例如，输入 2、2、4、7 可以以多种方式使用以获得 24:

2+2*(4+7) = 24

2+2*(7+4) = 24

(2+2)*7-4 = 24

(2*2)*7-4 = 24

2*(2*7)-4 = 24

还有 4 个数字的组合不能得出等于 24 的任何等式。例如 1,1,1,1。在这种情况下，您的程序应该返回不存在等于 24 的可能方程。

注意:虽然我们将输入 1 到 9 之间的 4 个整数，但我们将使用 double 来计算所有运算。例如，数字3、3、8、8可以组合成公式:8/(3-8/3) = 24。

工作流程:您的程序应从用户那里读取 4 个数字，并输出结果为 24 的公式。该算法应枚举 4 个数字的所有可能顺序、所有可能的组合和所有可能的公式。

这让我得到了数字 a、b、c、d 的 24 种排列和运算符 +-/* 的 64 种排列。我得出这个结论的原因是 4^3 4 个运算符在方程式中只有 3 个填充点。除了今天，我在编写评估方法和计算方程式中的 parent 时遇到了麻烦。

这是我的代码:

public static void evaluate(cbar [][] operations , double [][] operands)
{
    /*
    This is the part that gets me how am I supposed to account
    for parentases and bring all these expressions togather to
    actually form and equation.
    */
}

最佳答案

这个问题提出了几个挑战。我下面的解决方案大约有两百行。它可能比作业要求的要长一点，因为我将它概括为任意数量的术语。我鼓励您研究算法并编写自己的解决方案。

我们必须克服的主要障碍如下。

• 我们如何生成不重复的排列？

• 我们如何构建和评估算术表达式？

• 我们如何将表达式转换为唯一的字符串？

有很多方法可以生成排列。我选择了递归方法，因为它很容易理解。主要的并发症是术语可以重复，这意味着可能少于 4! = 4*3*2*1 排列。例如，如果条件是 1 1 1 2，则只有四种排列。

为避免重复排列，我们首先对术语进行排序。递归函数从左到右查找所有重复项的位置，无需回溯。例如，一旦第一个 1 被放入数组中，所有剩余的 1 项都被放置在它的右边。但是当我们到达 2 项时，我们可以回到数组的开头。

为了构建算术表达式，我们使用了另一个递归函数。此函数查看排列的两个项之间的每个位置，将数组拆分为该位置左侧的一段和右侧的一段。它进行一对递归调用来为左段和右段构建表达式。最后，它将生成的子表达式与四个算术运算符中的每一个连接起来。基本情况是数组大小为 1，因此不能拆分。这导致节点没有运算符也没有子节点，只有一个值。

由于浮点除法的不精确性，通过对 double 值执行算术计算表达式会出现问题。例如，1.0/3 = 0.33333...，但 3 * 0.33333... = 0.99999...。这使得在使用 double 值时很难确定 1/3 * 3 = 1。为了避免这些困难，我定义了一个 Fraction 类。它对分数进行算术运算，并始终通过最大公约数简化结果。除以零不会产生错误消息。相反，我们存储分数 0/0。

拼图的最后一 block 是将表达式转换为字符串。我们想要制作规范化或规范化的字符串，这样我们就不会不必要地重复自己。例如，我们不想显示 1 + (1 + (1 + 2)) 和 ((1 + 1) + 1) + 2，因为这些本质上是相同的表达。我们只想显示 1 + 1 + 1 + 2，而不是显示所有可能的括号。

我们可以通过仅在必要时添加括号来实现这一点。也就是说，如果具有较高优先级运算符(乘法或除法)的节点是具有较低优先级运算符(加法或减法)的节点的父节点，则括号是必需的。我所说的优先级是指运算符优先级，也称为操作顺序。高优先级的运算符比低优先级的运算符绑定(bind)得更紧密。所以如果父节点的优先级高于子节点的运算符，就需要给子节点加上括号。为确保我们最终得到唯一的字符串，我们在将它们添加到结果列表之前对照哈希集检查它们。

以下程序 Equation.java 接受用户在命令行上的输入。游戏的参数在 Equation 类的第一行。您可以修改这些以构建包含更多项、更大项和不同目标值的表达式。

import java.lang.*;
import java.util.*;
import java.io.*;

class Fraction {                  // Avoids floating-point trouble.
  int num, denom;
  static int gcd(int a, int b) {  // Greatest common divisor.
    while (b != 0) {
      int t = b;
      b = a % b;
      a = t;
    }
    return a;
  }
  Fraction(int num, int denom) {  // Makes a simplified fraction.
    if (denom == 0) {             // Division by zero results in
      this.num = this.denom = 0;  //  the fraction 0/0. We do not
    } else {                      //  throw an error.
      int x = Fraction.gcd(num, denom);
      this.num = num / x;
      this.denom = denom / x;     
    }
  }
  Fraction plus(Fraction other) {
    return new Fraction(this.num * other.denom + other.num * this.denom,
        this.denom * other.denom);
  }
  Fraction minus(Fraction other) {
    return this.plus(new Fraction(-other.num, other.denom));
  }
  Fraction times(Fraction other) {
    return new Fraction(this.num * other.num, this.denom * other.denom);
  }
  Fraction divide(Fraction other) {
    return new Fraction(this.num * other.denom, this.denom * other.num);
  }
  public String toString() {      // Omits the denominator if possible.
    if (denom == 1) {
      return ""+num;
    }
    return num+"/"+denom;
  }
}

class Expression {                // A tree node containing a value and
  Fraction value;                 //  optionally an operator and its
  String operator;                //  operands.
  Expression left, right;
  static int level(String operator) {
    if (operator.compareTo("+") == 0 || operator.compareTo("-") == 0) {
      return 0;                   // Returns the priority of evaluation,
    }                             //  also known as operator precedence
    return 1;                     //  or the order of operations.
  }
  Expression(int x) {             // Simplest case: a whole number.
    value = new Fraction(x, 1);
  }
  Expression(Expression left, String operator, Expression right) {
    if (operator == "+") {
      value = left.value.plus(right.value);
    } else if (operator == "-") {
      value = left.value.minus(right.value);
    } else if (operator == "*") {
      value = left.value.times(right.value);
    } else if (operator == "/") {
      value = left.value.divide(right.value);
    }
    this.operator = operator;
    this.left = left;
    this.right = right;
  }
  public String toString() {      // Returns a normalized expression,
    if (operator == null) {       //  inserting parentheses only where
      return value.toString();    //  necessary to avoid ambiguity.
    }
    int level = Expression.level(operator);
    String a = left.toString(), aOp = left.operator,
           b = right.toString(), bOp = right.operator;
    if (aOp != null && Expression.level(aOp) < level) {
      a = "("+a+")";              // Parenthesize the child only if its
    }                             //  priority is lower than the parent's.
    if (bOp != null && Expression.level(bOp) < level) {
      b = "("+b+")";
    }
    return a + " " + operator + " " + b;
  }
}

public class Equation {

  // These are the parameters of the game.
  static int need = 4, min = 1, max = 9, target = 24;

  int[] terms, permutation;
  boolean[] used;
  ArrayList<String> wins = new ArrayList<String>();
  Set<String> winSet = new HashSet<String>();
  String[] operators = {"+", "-", "*", "/"};

  // Recursively break up the terms into left and right
  //  portions, joining them with one of the four operators.
  ArrayList<Expression> make(int left, int right) {
    ArrayList<Expression> result = new ArrayList<Expression>();
    if (left+1 == right) {
      result.add(new Expression(permutation[left]));
    } else {
      for (int i = left+1; i < right; ++i) {
        ArrayList<Expression> leftSide = make(left, i);
        ArrayList<Expression> rightSide = make(i, right);
        for (int j = 0; j < leftSide.size(); ++j) {
          for (int k = 0; k < rightSide.size(); ++k) {
            for (int p = 0; p < operators.length; ++p) {
              result.add(new Expression(leftSide.get(j),
                    operators[p],
                    rightSide.get(k)));
            }
          }
        }
      }
    }
    return result;
  }

  // Given a permutation of terms, form all possible arithmetic
  //  expressions. Inspect the results and save those that
  //  have the target value.
  void formulate() {
    ArrayList<Expression> expressions = make(0, terms.length);
    for (int i = 0; i < expressions.size(); ++i) {
      Expression expression = expressions.get(i);
      Fraction value = expression.value;
      if (value.num == target && value.denom == 1) {
        String s = expressions.get(i).toString();
        if (!winSet.contains(s)) {// Check to see if an expression
          wins.add(s);            //  with the same normalized string
          winSet.add(s);          //  representation was saved earlier.
        }
      }
    }
  }

  // Permutes terms without duplication. Requires the terms to
  //  be sorted. Notice how we check the next term to see if
  //  it's the same. If it is, we don't return to the beginning
  //  of the array.
  void permute(int termIx, int pos) {
    if (pos == terms.length) {
      return;
    }
    if (!used[pos]) {
      permutation[pos] = terms[termIx];
      if (termIx+1 == terms.length) {
        formulate();
      } else {
        used[pos] = true;
        if (terms[termIx+1] == terms[termIx]) {
          permute(termIx+1, pos+1);
        } else {
          permute(termIx+1, 0);
        }
        used[pos] = false;
      }
    }
    permute(termIx, pos+1);
  }

  // Start the permutation process, count the end results, display them.
  void solve(int[] terms) {
    this.terms = terms;           // We must sort the terms in order for
    Arrays.sort(terms);           //  the permute() function to work.
    permutation = new int[terms.length];
    used = new boolean[terms.length];
    permute(0, 0);
    if (wins.size() == 0) {
      System.out.println("There are no feasible expressions.");
    } else if (wins.size() == 1) {
      System.out.println("There is one feasible expression:");
    } else {
      System.out.println("There are "+wins.size()+" feasible expressions:");
    }
    for (int i = 0; i < wins.size(); ++i) {
      System.out.println(wins.get(i) + " = " + target);
    }
  }

  // Get user input from the command line and check its validity.
  public static void main(String[] args) {
    if (args.length != need) {
      System.out.println("must specify "+need+" digits");
      return;
    }
    int digits[] = new int[need];
    for (int i = 0; i < need; ++i) {
      try {
        digits[i] = Integer.parseInt(args[i]);
      } catch (NumberFormatException e) {
        System.out.println("\""+args[i]+"\" is not an integer");
        return;
      }
      if (digits[i] < min || digits[i] > max) {
        System.out.println(digits[i]+" is outside the range ["+
            min+", "+max+"]");
        return;
      }
    }
    (new Equation()).solve(digits);
  }
}

关于java - 用 Java 构建数学游戏，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27160339/