Algoritma - Tek değişkenli lineer denklem çözme

Question

Bir dize şeklinde bir ifade verildiğinde, x için çözün. İfadedeki en yüksek x gücü 1'e eşit olacaktır. İzin verilen işleçler +, * ve -. Bunların hepsi ikili işleçlerdir. Yani 2x x * x olarak yazılır. Her operatör tek bir dönem veya bir sabitle takip edilecektir.

Örneğin, aşağıdaki eşitlik dikkate:

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

Bu mükemmel geçerlidir denklem. 1 * 2 * 3 formundaki ifadeler geçersizdir, ancak 1 * (2 * 3) geçerlidir. Böyle bir denklem verildiğinde, x'e bir çözüm bulmamız gerekir. Denklem geçersiz ise, program bir hata mesajı görüntülemelidir.

Birisi bu sorunun nasıl çözülebileceği konusunda herhangi bir fikir verebilir mi? Şu anda aklıma gelen tek şey, Bağlamsız Dilbilgisi Gramlerini Kullanarak Sözcük Analizi ve Ayrıştırmadır. Ama bence bundan daha kolay bir çözüm var. Birisi üzerinde ışık tutabilir mi?

Answer 1

(1) 'u e = 0'a dönüştürün e = e1 - e2.

(2) Bazı a ve b için ax + b, e dönüştürün.

(3) Çöz, x = -b/a.

Kademe (2) Bu gibi akıcı bir şekilde ele alınabilir:

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)