CODEWITHSUNDEEP
data-structures
Hatefiend
Hatefiend

Reputation: 3596

Data structure for an Algebra equation?

I'm trying to make an application that is fed in an algebra equation and solves for a given variable of the users choosing.

Pseudocode below

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

For example the average equation might be:

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

I need to store this information in some sort of data structure however in order to parse through it. As you see above when I wrote LinkedList<Term>, it works but there's no way for me to implement operators.

Using the above example, this is how I want my data structure to look like:

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

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

I can't do this though, because LinkedList needs to be of one data type, which needs to be expression. How should i represent operators?

Upvotes: 2

Views: 839

Answers (1)

templatetypedef
templatetypedef

Reputation: 372992

It is significantly easier to work with expressions when you have them represented as abstract syntax trees, tree structures that show the underlying structures of formulas. I would strongly recommend investigating how to use ASTs here; you typically build them with a parsing algorithm (Dijkstra's shunting-yard algorithm might work really well for you based on your setup) and then use either abstract methods or the visitor pattern to traverse the ASTs to perform the computations you need.

ASTs are often represented by having either an interface or an abstract class representing a node in the tree, then having subclasses for each operator you'd encounter (they represent internal nodes) and subclasses for concepts like "number" or "variable" (typically, they're leaves).

If you'd like to get a sense of what this might look like, I implemented a tool to generate truth tables for propositional logic formulas using these techniques. The JavaScript source shows off how to use ASTs and the shunting-yard algorithm.

Upvotes: 4

Related Questions