data-structures - 代数方程的数据结构？

Question

我正在尝试制作一个应用程序，该应用程序输入代数方程并求解用户选择的给定变量。

下面的伪代码

enum Variable
    x, pi, y, z; //.. etc

class Value
double constant;
Variable var;

class Term
Value val;              // Might be a variable or a constant
Expression exponent;    // The exponent of this term
boolean sign;           // Negative flag

class Expression
LinkedList<Term>;       // All the terms in this expression
^ This is what I need help on.

Expression exponent;    // The exponent of this term

例如，平均方程可能是:

y           =       x        +              (x - 5)^z
^term               ^term    ^ operator     ^ expression^term

我需要将这些信息存储在某种数据结构中，以便对其进行解析。正如你在上面我写 LinkedList<Term> 时看到的那样，它有效，但我无法实现运算符。

使用上面的示例，这就是我希望我的数据结构的样子:

// Left side of the equals sign
{ NULL <-> y <-> NULL }

// Right side of the equals sign
{ NULL <-> x <-> Operator.ADD <-> Expression: (x - 5) <-> NULL }

但我不能这样做，因为 LinkedList需要是一种数据类型，并且需要是表达式。我应该如何代表运营商？

Answer 1

当您将表达式表示为抽象语法树(显示公式底层结构的树结构)时，使用表达式会变得更加容易。我强烈建议在这里研究如何使用 AST；您通常使用解析算法构建它们(根据您的设置，Dijkstra 的分流场算法可能非常适合您)，然后使用抽象方法或访问者模式来遍历 AST 来执行您需要的计算。

AST 通常由代表树中节点的接口(interface)或抽象类来表示，然后为您遇到的每个运算符(它们代表内部节点)和“数字”或“变量”等概念的子类提供子类“(通常，它们是叶子)。

如果您想了解一下这可能是什么样子，我实现了 tool to generate truth tables for propositional logic formulas使用这些技术。 JavaScript source展示如何使用 AST 和调车场算法。