算法 - 解一元线性方程

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的解。如果该方程无效，则程序应显示错误消息。

有人能提供任何关于如何解决这个问题的想法吗？目前我脑海中唯一能想到的是词法分析和使用上下文无关语法进行解析。但我有一种感觉比那要简单得多。有人能给出一些提示吗？

- Diptesh Chatterjee

---

解析似乎是第一步正确的方法。 - Xymostech

Answer 1

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

- Rafe