求解一元线性方程的算法

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 where e = e1 - e2。

(2)将e转换为ax + b，对于某些a和b。

(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)