algorithm - 求解表示为字符串的线性方程

Question

我得到一个字符串 2*x + 5 - (3*x-2)=x + 5，我需要求解 x。我的想法是将其转换为表达式树，例如，

          =
        /  \
       -    +
      /\    /\
     +  -   x  5
    /\  /\ 
   *  5 * 2
  /\   /\
 2  x  3 x

但是我如何真正从这里减少树呢？还有其他想法吗？

Answer 1

你必须使用代数中的公理来减少它

a * (b + c) -> (a * b) + (a * c)

这是通过检查传递树中每个节点的类型来完成的。一旦事物完全扩展为术语，您就可以检查它们实际上是线性的，等等。

树中的值将是变量或数字。然而，将它们表示为从某些 AbstractTreeNode 类继承的类并不是很整洁，因为 cplusplus 没有多重分派(dispatch)。所以最好以 'c' 方式进行。

enum NodeType {
    Number,
    Variable,
    Addition //to represent the + and *
}

struct Node {
    NodeType type;
    //union {char*,  int, Node*[2]} //psuedo code, but you need
    //something kind of like this for the 
    //variable name ("x") and numerical value
    //and the children
}

现在您可以使用 switch case 查询节点及其子节点的类型。

正如我之前所说 - C++ 惯用代码将使用虚函数，但缺乏必要的多重分派(dispatch)来干净地解决这个问题。 (无论如何你都需要存储类型)

然后将项等分组并求解方程。

例如，您可以有规范化树的规则

constant + variable -> variable + constant

将 x 始终放在术语的左侧。然后 x * 2 + x * 4 可以更容易地简化

var * constant + var * constant -> (sum of constants) * var

在你的例子中......

首先，通过移动术语(按照上述规则)简化“=”

右侧将是 -1 * (x + 5)，变为 -1 * x + -1 * 5。左侧将更难 - 考虑将 a - b 替换为 a + -1 * b。

最终，

2x + 5 + -3x + 2 + -x + -5 = 0

然后您可以按照自己的方式对术语进行分组。 (通过扫描等)

(2 + -3 + -1) x + 5 + 2 + -5 = 0

将它们总结起来，当你有 mx + c 时，解决它。