重排简单符号代数表达式的算法

Question

我想知道是否有一种简单的算法可以重新排列简单的符号代数表达式。理想情况下，我希望能够将任何这样的表达式重写为只有一个变量在左侧。例如，给定输入：

m = (x + y) / 2

我希望能够根据m和y来询问关于x的问题，或者根据x和m来询问关于y的问题，并且能够得到如下结果：

x = 2*m - y
y = 2*m - x

当然，我们多年来一直在纸上完成这个算法。但我想知道它是否有一个名称。它看起来很简单，但如果有人已经归档了各种“陷阱”，那么就会更容易。

对于我的目的，我不需要它处理二次方程。

（是的，CAS系统可以做到这一点，是的，我知道我可以将它们用作库。但我希望避免在我的应用程序中出现这样的依赖性。我真的只想知道是否有命名算法来解决这个问题。）

- Gabe Johnson

---

那些被命名的算法是在计算机代数系统中实现的。这是一种“非本土发明”的情况吗？ - Mitch Wheat

Answer 1

似乎您感兴趣的是维护一组线性方程，并且随时能够解出一个变量关于其他所有变量的表达式。如果将这些关系编码为矩阵，则可以将矩阵化简为某种良好的形式（例如，行最简形），以获得变量之间“最简单”的依赖关系（对于“最简单”的良好定义）。有了这样的数据，您只需查看某个具有所需变量非零条目的行，然后将其归一化，使该变量系数为1，就可以读取所有依赖关系。

请注意-通常情况下，每个变量并不总是都有唯一的解。例如，给定平凡方程组：

x = y
x = z

然后解出 z 可能会得到 "z = x" 或者 "z = y"，取决于想要多少简化。或者在类似下面的设置中：

x = 2y + 3w
x = 9z

返回变量x的值可以是一个表达式，或它们两个的和，或其他很多东西，这些东西在技术上都是正确的，但不一定有用。我不确定你该如何处理这种情况，但根据你的方程式形式，你可能会找到一种处理方法。

- templatetypedef

Answer 2

您需要的是方程求解算法。但我敢打赌这是一个庞大的主题。一般情况下，可能会有以下内容：

- 方程组 - 方程可能是非线性的，因此需要额外的算法，如方程分解。 - 需要知道如何反转函数，例如：sin（x）+10 = z，解出x时我们需要反转sin（），即arcsin（）。 （并非所有函数都可逆！） - 最后，有些方程甚至对于CAS来说也很难求解，例如sin（x）+x = y，求解x。

较困难的答案是 - 您最好从某些CAS的源代码中获取源代码，例如您可以查看用LISP编写的MAXIMA CAS源代码。并找到负责方程求解的代码。

简单的答案是 - 如果您需要解决仅由基本运算符+-*/组成且为线性的方程，则已经知道答案 - 使用旧的纸张方法 - 考虑我们在纸上使用的规则，并将这些规则重新编写为操作方程字符串的符号算法。

祝你好运！

- Agnius Vasiliauskas

---

我进行了更多的研究，发现约束求解器都可以处理这种情况。由于我的应用程序将在很大程度上依赖于约束条件，因此我可以使用像Choco或JaCoP这样的工具。你说得对，这是一个庞大的主题，我相信你的直觉（以及下面的另一个答案）是正确的，方程组就是关键所在。 - Gabe Johnson

Answer 3

将您的表达式转换为逆波兰表示法的数据结构（树）。您的树由节点组成，每个节点都有一个操作、一个左子节点和一个右子节点。左右子节点可以是符号（例如："x"）或另一个节点。例如：

(x + (a + b))

会变成：

(+ x (+ a b))

或者用JSON表示：

["+", "x", ["+", "a", "b"]]

你原始的表达式m = (x + y) / 2会变成这样：

m = ["/", ["+", "x", "y"], "2"]

您所期望的表达式（解出x）如下：

x = ["-", ["*", "m", "2"], "y"]

你能看到表达式树已经被颠倒过来，每个运算符都被反转了吗？"-"是"+"的反转，现在包裹着"*"，它是"/"的反转。这样做：

["+", "x", "y"]

成为：

变成：

["-", (something), "y"]

其中（something）是外部表达式的递归反转。尝试解释该过程：a）递归地遍历表达式树，直到找到包含想要解决的符号的节点，b）创建一个新的节点，并反转该节点的操作，c）用反转的外部表达式替换想要解决的符号，在向外进展时递归执行此操作。

- Chris E

Answer 4

我有一个类似的需求，需要重新排列方程以改变主题。我已经创建了一个带有示例Dart代码的gist，你可以在DartPad上运行它这里。请注意，Dart是一种类似于Javascript和Java的语言，所以希望你能理解它。

这段代码允许你构建一个由Node组成的表达式树，每个Node都有一个表示运算符或变量的字符串token，并且可能有一个或两个操作数子Node。（如果你需要将文本转换为表达式的代码，构建Node，我可以稍后添加。）

方程的主题或“lhs”不在表达式中，而是在“rhs”中。操作rearrangeNode可以改变方程的主题，提取newSubject并插入oldSubject。

以下是方便起见的代码：

class ExpressionInvalid implements Exception {
  final String msg;
  ExpressionInvalid(this.msg);
}

class Node {
  final String token;
  Node? left;
  Node? right;

  Node(this.token, [this.left, this.right]);

  Node? findNode(String subject) {
    Node? sNode;
    int count = 0;
    for (var node in [left, right]) {
      if (node != null) {
        var nNode = node.findNode(subject);
        if (nNode != null) {
          count++;
          sNode = nNode;
        }
      }
    }
    if (token == subject) {
      count++;
      sNode = this;
    }
    if (count > 1) throw ExpressionInvalid('More than one node for $subject');
    return sNode;
  }

  Node? rearrangeNode(String newSubject, String oldSubject, Node? child) {
    if (token == newSubject) {
      if (child != null) return child;
      return Node(newSubject);
    }
    if (left != null) {
      if (left!.findNode(newSubject) != null) {
        var newToken = token;
        if (token == "+") newToken = "-";
        if (token == "-" && right != null) newToken = "+";
        if (token == "*") newToken = "/";
        if (token == "/") newToken = "*";
        var other = child ?? Node(oldSubject);
        child = Node(newToken, other, right);
        return left!.rearrangeNode(newSubject, oldSubject, child);
      }
    }
    if (right != null) {
      if (right!.findNode(newSubject) != null) {
        var newToken = token;
        if (token == "+") newToken = "-";
        if (token == "-") newToken = "-";
        if (token == "*") newToken = "/";
        if (token == "/") newToken = "/";
        var other = child ?? Node(oldSubject);
        if (token == "+") child = Node(newToken, other, left);
        if (token == "-") child = Node(newToken, left, other);
        if (token == "*") child = Node(newToken, other, left);
        if (token == "/") child = Node(newToken, left, other);
        return right!.rearrangeNode(newSubject, oldSubject, child);
      }
    }
    return null;
  }

  @override
  String toString() =>
      "($token${left != null ? ' $left' : ''}${right != null ? '$right' : ''})";
}

void main() {
  var tree1 = Node("-", Node("-", Node("x"), Node("N")), Node("y"));
  var tree2 = Node("+", Node("C"), Node("-", Node("-", Node("N"), Node("g")), Node("h")));
  var tree3 = Node("*", Node("j"), Node("+", Node("N"), Node("c")));
  var tree4 = Node("*", Node("a"), Node("-", Node("N")));
  for (var tree in [tree1, tree2, tree3, tree4]) {
    var newTree = tree.rearrangeNode("N", "O", null);
    print("O = $tree => N = $newTree");
  }
}

- Patrick O'Hara

Answer 5

有许多简单的方法可以修改初始方程，正确的顺序进行正确的修改将导致正确的解决方案。那么把它看作是一个搜索或路径查找问题怎么样？

- alan2here