c++ - 表达式转换问题

Question

假设我们有以下语句:s = 3 * a * b - 2 * c，其中 s, a, b 和 c 是变量。此外，我们使用了 Shunting Yard构建算法 RPN表达式，所以现在我们可以为变量 a、b 和 c 赋值，并使用简单的方法计算 s 值RPN 评估器。

但是，问题是我应该能够计算任何变量 a、b 或 c 的值设置了其他变量。

因此，我需要以某种方式转换现有表达式以获得一组表达式:

a = (s + 2 * c) / (3 * b)
b = (s + 2 * c) / (3 * a)
c = (3 * a * b - s) / 2

如何根据一个原始语句生成这样的表达式？是否有解决此类问题的标准方法？

约束:

1. 一组可用的运算符:+、-、*、/，包括一元 + 和 -
2. 运算符 *、/ 和 = 两边不能有相同的变量(例如 s = a * a 或 s = a + s 是 Not Acceptable )

谢谢

Answer 1

先看这个:Postfix notation to expression tree将您的 RPN 转换为树。

一旦你有了等式 left expression = right expression 将其更改为 left expression - right expression = 0 并创建一个 left expression - right expression 树 通过调车场和上面的答案。因此，当您评估树时，您必须得到答案为 0。

现在根据您的限制，观察如果变量(例如 x)未知，则结果表达式将始终采用以下形式

(ax + b)/(cx + d) 其中 a、b、c、d 将取决于其他变量。

您现在可以递归地将表达式计算为元组 (a,b,c,d)。

最后，你会解出线性方程

(ax + b)/(cx + d) = 0 给出 x = -b/a

这样您就不必为每个变量计算单独的表达式。一个表达式树就足够了。给定其他变量，您只需递归计算元组 (a,b,c,d)，最后求解线性方程。

(不完整的)伪代码将是

TupleOrValue Eval (Tree t) {

       if (!t.ContainsVariable) {
           blah;
           return value;
       }

       Tuple result;

       if (t.Left.ContainsVariable) {
            result = Eval(t.Left);  
            value = Eval(t.Right);

            return Compose(t.Operator, result, value);      
       } else {
            result = Eval(t.Right);  
            value = Eval(t.Left);

            return Compose(t.Operator, result, value);      
       }
}

Tuple Compose(Operator op, Tuple t, Value v) {

    switch (op) {

        case 'PLUS': return new Tuple(t.a + v*t.c, t.b + v*t.d, t.c, t.d);
                    // (ax+b)/(cx+d) + v = ( (a + vc)x + b + dv)/(cx + d)
        // blah
    }
}

举个例子，如果表达式是x+y-z = 0。树将是

     +
    /  \
   x    -
       / \
       y  z

对于 y=5 和 z=2。

Eval (t.Right) 将返回 y-z = 3，因为该子树不包含 x。

Eval(t.Left) 将返回对应于 (1x + 0)/(0x + 1) 的 (1,0,0,1)。注意:上面的伪代码是不完整的。

现在将 (1,0,0,1) 与值 3 组合将得到 (1 + 3*0, 0 + 3*1, 0, 1) = (1,3,0,1 ) 对应于 (x + 3)/(0x + 1)。

现在，如果你想解决这个问题，你可以将 x 设为 -b/a = -3/1 = -3

---

我会留下原来的答案:

一般来说这是不可能的。

例如考虑表达式

x*x*x*x*x + a*x*x*x*x + b*x*x*x + c*x*x + d*x = e

得到x的表达式基本上对应于求多项式的根

x⁵ + ax⁴ + bx³ + cx² + dx -e

如果您想使用 +、-、/、* 和 n 次根，这已被证明通常是不可能的。参见 Abel Ruffini定理。

是否有一些您忘记提及的限制可能会简化问题？