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)转换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)
于 2012-12-03T00:59:11.853 回答