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

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没有多个分派.因此最好以"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 ++惯用代码将使用虚函数,但缺乏必要的多次调度来干净地解决这个问题.(无论如何你都需要存储类型)

然后你将术语等分组并解决方程式.

例如,您可以使用规则来规范化树

constant + variable -> variable + constant

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

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

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

首先,通过移动术语来简化'='(根据上面的规则)

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

最终,

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

然后,您可以按照您想要的方式对术语进行分组.(通过扫描等)

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

总结它们,当你有mx + c时,解决它.