算法 - 求解一个变量的线性方程

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的解决方案.如果等式无效,程序应显示错误消息.

有人可以解释如何解决这个问题吗？我现在唯一想到的就是使用Context Free Grammars进行词法分析和解析.但我觉得有一个比这更简单的解决方案.有人可以对它有所启发吗？

Answer 1

(1) 转换e1 = e2为e = 0其中e = 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)