Datenstruktur für eine Algebra-Gleichung?

Question

Ich versuche, eine Anwendung, die in einer Algebra-Gleichung eingespeist wird und löst für eine bestimmte Variable der Benutzer zu wählen.

Pseudocode unten

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 

Zum Beispiel der durchschnittliche Gleichung könnte sein:

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

Ich brauche diese Informationen in irgendeiner Art von Datenstruktur zu speichern, jedoch um durch sie zu analysieren. Wie Sie oben sehen, wenn ich LinkedList<Term> schrieb, funktioniert es, aber es gibt keine Möglichkeit für mich, Operatoren zu implementieren.

das obige Beispiel verwenden, das ist, wie ich meine Datenstruktur aussehen soll:

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

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

ich dies aber nicht tun können, weil LinkedList Bedürfnisse eines Datentyps sein, was sein muss Ausdruck. Wie sollte ich Operatoren darstellen?

Answer 1

Es ist wesentlich einfacher, mit Ausdrücken zu arbeiten, wenn Sie sie als abstrakte Syntaxbäume darstellen, Baumstrukturen, die die zugrunde liegenden Strukturen von Formeln zeigen. Ich würde dringend empfehlen, hier zu untersuchen, wie man ASTs benutzt; Sie bauen sie normalerweise mit einem Parsing-Algorithmus auf (Dijkstra's Rangieryard-Algorithmus funktioniert auf Grund Ihrer Konfiguration sehr gut) und verwendet dann entweder abstrakte Methoden oder das Besuchermuster, um die ASTs zu durchlaufen, um die benötigten Berechnungen durchzuführen.

ASTs werden oft dadurch dargestellt, dass entweder eine Schnittstelle oder eine abstrakte Klasse einen Knoten in der Struktur darstellt, dann Unterklassen für jeden Operator (sie repräsentieren interne Knoten) und Unterklassen für Konzepte wie "Zahl" oder " Variable "(normalerweise sind sie Blätter).

Wenn Sie ein Gefühl dafür bekommen möchten, wie dies aussehen könnte, habe ich eine tool to generate truth tables for propositional logic formulas mit diesen Techniken implementiert. Die JavaScript source zeigt, wie man ASTs und den Shunting-Yard-Algorithmus verwendet.