代数方程的数据结构？

问题描述：

我正在尝试创建一个代数方程中的应用程序，并解决用户选择的给定变量。代数方程的数据结构？

下面的伪代码

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需求是一个数据类型，它需要是的表达。我应该如何表示运营商？

我可以建议作为Term的子类吗？作为一种关系，它必然有约束力来拥有前一个和下一个元素？ – Flint

我在理解你的意思时有点困难吗？你的意思是让我的Term类有两个字段（右侧和左侧）来通知它左侧或右侧的操作员？ – Hatefiend

在您的示例中，术语处于链接列表中。最终，链接列表的元素自己引用该列表的前一个和下一个元素。假设运算符是带有附加规则的术语（子类）：它们在两侧都有字面词或表达式。现在，忘记我说的话，遵循templatetypedef的建议，而使用抽象语法树：树叶和节点自然会携带这些属性。 – Flint

答

当您将它们表示为抽象语法树和显示公式基础结构的树结构时，使用表达式显着更容易。我强烈建议在这里调查如何使用AST;您通常使用解析算法（Dijkstra的分流码算法可能基于您的设置对您很有用）构建它们，然后使用抽象方法或访问者模式来遍历AST以执行所需的计算。

AST常常表示为具有表示树中节点的接口或抽象类，然后为每个将遇到的操作符（它们表示内部节点）提供子类，并为“数字”或“变量“（通常是叶子）。

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

嘿，谢谢你的回复。我是第三年CS学生，但我以前没有听说过这些。我在网上查看，只能发现AST在尝试为其实施之前会出现问题*。这是你的意思吗？我需要更多地考虑充实这个想法吗？我很困惑。 – Hatefiend

AST在实际软件中明确用于解决各种问题（它们在编译器中用于表示输入程序）。我怀疑你可能需要做更多的搜索。 – templatetypedef

只要确定，AST就像Java中的TreeMap一样，但没有提供的类型，对吧？防爆。 'TreeMap x = new TreeMap;' – Hatefiend

代数方程的数据结构？

相关推荐