10

文字列形式の式が与えられた場合、x について解きます。式の x の最大べき乗は 1 になります。使用できる演算子は +、*、および - です。これらはすべて二項演算子です。したがって、2x は 2*x と記述されます。すべての演算子の後には、単一の項または定数が続きます。

たとえば、次の式を考えてみましょう。

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

これは完全に有効な方程式です。1*2*3 の形式の式は無効ですが、1*(2*3) は有効です。

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

誰かがこの問題を解決する方法について何か考えを与えることができますか? 今頭に浮かんでいるのは、文脈自由文法を使用した字句解析と構文解析だけです。しかし、それよりもはるかに簡単な解決策があると感じています。誰かがそれに光を当てることができますか？

4

1 に答える 1

5

(1) where に変換e1 = e2します。e = 0e = e1 - e2

(2)一部のおよびについて、 に変換eします。ax + bab

(3) を解く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)
于 2012-12-03T00:59:11.853 に答える