Algorytm - rozwiązywanie równania liniowego w jednej zmiennej

Question

Podając wyrażenie w postaci ciągu, należy rozwiązać x. Najwyższa potęga x w wyrażeniu będzie równa 1. Operatory dozwolone to +, * i -. Są to wszystkie operatory binarne. Tak więc 2x byłoby napisane jako 2 * x. Po każdym operatorze następuje pojedynczy termin lub stała.

Na przykład, należy rozważyć następujące równanie:

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

ten jest w pełni uzasadniona równanie. Wyrażenia w formularzu 1 * 2 * 3 są nieprawidłowe, ale 1 * (2 * 3) jest ważny.

Biorąc pod uwagę takie równanie, musimy znaleźć rozwiązanie x. Jeśli równanie jest nieprawidłowe, program powinien wyświetlić komunikat o błędzie.

Czy ktoś może dać pojęcie o tym, jak rozwiązać ten problem? Jedyne, co przychodzi mi teraz na myśl, to analiza leksykalna i parsowanie przy użyciu gramatyk bezkontekstowych. Ale mam wrażenie, że jest o wiele łatwiejsze rozwiązanie. Czy ktoś może rzucić na to trochę światła?

Answer 1

(1) Konwertuj e1 = e2 na e = 0, gdzie e = e1 - e2.

(2) Konwertuj e na ax + b, dla niektórych a i b.

(3) Rozwiąż, x = -b/a.

Etap (2) mogą być obsługiwane rekurencyjnie w następujący sposób:

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)