Algorithmus - Lösen der linearen Gleichung in einer Variablen

Question

Gegeben ein Ausdruck in Form einer Zeichenkette, löse nach x. Die höchste Potenz von x im Ausdruck wird gleich 1 sein. Zulässige Operatoren sind +, * und -. Dies sind alles binäre Operatoren. Also würde 2x als 2 * x geschrieben werden. Auf jeden Operator folgt ein einzelner Ausdruck oder eine Konstante.

Betrachten wir zum Beispiel die folgende Gleichung:

2 * x + 5- (4 * x-7 + (4-2)) = 10 * x-9

Dies ist eine absolut gültige Gleichung. Ausdrücke der Form 1 * 2 * 3 sind ungültig, aber 1 * (2 * 3) ist gültig.

Angesichts einer solchen Gleichung müssen wir eine Lösung für x finden. Wenn die Gleichung ungültig ist, sollte das Programm eine Fehlermeldung anzeigen.

Kann jemand eine Idee darüber geben, wie dieses Problem gelöst werden kann? Das einzige, was mir gerade in den Sinn kommt, ist Lexikalische Analyse und Parsing mit kontextfreien Grammatiken. Aber ich habe das Gefühl, dass es eine viel einfachere Lösung gibt. Kann jemand etwas Licht darauf werfen?

Answer 1

(1) Konvertieren e1 = e2 in e = 0 wo e = e1 - e2.

(2) Konvertieren e in ax + b, für einige a und b.

(3) Lösung, x = -b/a.

Schritt (2) kann rekursiv behandelt werden, wie folgt aus:

F(k)  = 0x + k // For any constant k. 
F(x)  = 1x + 0 
F(p + q) = let a_1x + b_1 = F(p) 
      and a_2x + b_2 = F(q) 
      in (a_1 + a_2)x + (b_1 + b_2) 
    // Similarly for subtraction. 
F(p * q) = let a_1x + b_1 = F(p) 
      and a_2x + b_2 = F(q) // At least one of a_1 and a_2 must be zero. 
      in (a_1*b_2 + a_2*b_1)x + (b_1*b_2)