アルゴリズム - 1つの変数で線形方程式を解く

Question

文字列の形の式が与えられた場合、xを解く。式のxの最大の累乗は1になります。使用できる演算子は+、*、 - です。これらはすべてバイナリ演算子です。したがって、2xは2 * xと書かれます。すべての演算子の後には、単一の項または定数が続きます。

は、例えば、以下の式を考える：

2 * X + 5-（4 * X-7 +（4-2））= 10 * X-9

これは完全に有効です方程式。式1 * 2 * 3の式は無効ですが、1 *（2 * 3）は有効です。

このような式が与えられた場合、xの解を見つける必要があります。方程式が無効な場合、プログラムはエラーメッセージを表示する必要があります。

誰かがこの問題をどのように解決できるか考えていただけますか？今私の頭に浮かんでいるのは、文脈自由文法を使ったレキシカル分析と解析です。しかし、私はそこよりはるかに簡単な解決策があると感じています。誰かがそれに光を投げることができますか？

Answer 1

（1）e1 = e2をe = 0に変換します（e = e1 - e2）。

（2）をax + bに変換してください。aとbです。

（3）Solve、x = -b/a。

ステップは、（2）このように、再帰的に処理することができます。

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)