后缀表达式的求值变量

Question

我正在尝试为单变量方程建立求解器。我正在使用Shunting-yard算法，并根据denver和rici的建议进行了扩展。显然，该算法可以很好地解析给定数学表达式的谷底，确定其有效性并评估该值。但是，我很难理解如何结合求解某个变量。

[如果使用等式2 * (x - 4) = 4，则可以毫不费力地将其转换为RPN作为2 x 4 - * 4 -。从这里开始，很容易评估任何给定x的值。但是，如何确定x？我正在查看gab's答案，尽管我很清楚如何从RPN表单构建树，但我不知道如何计算值（他的答案中的步骤5）。

谢谢。

Answer 1

您用铅笔和纸解决此问题的方法：将东西移到等式的另一侧，直到只剩下x。您的树看起来像这样：

        =
      /   \
    *       4
   / \
  2   −
     / \
    x   4

所有分支都是运算符，所有叶子都是操作数。来自单个变量的路径经过左侧的*和−节点。这意味着您必须从左侧到右侧尽可能多地获取东西，理想情况下，直到只剩下x节点为止。

左侧的第一个节点是乘法运算符。您可以应用转换

a * b == c    ⟺    b = c / a

到树：删除左侧的乘法，并在右侧插入其逆运算，除以常数2。您的树现在看起来像这样：

        =
      /   \
    −       ÷
   / \     / \
  x   4   4   2

除法运算两个常数。您可以将它们“折叠”成结果，2 ::>

        =
      /   \
    −       2
   / \ 
  x   4 
（（如果只有一个变量，则可以在创建节点时执行此操作，这样就不会有一个要删除的÷节点的中间步骤。您还应该检测任何除法此处为零。）

现在以相同方式移动减法运算符：

        =
      /   \
    x       +
           / \
          2   4 
计算右边的常数表达式，您会得到x == 6。

因此，您基本上将最上面的左手运算符转换为其反函数，直到只剩下变量：

a + x == b   ⟺   x == b − a            x + a == b   ⟺   x == b − a
a − x == b   ⟺   x == a − b            x − a == b   ⟺   x == b + a
a * x == b   ⟺   x == b / a            x * a == b   ⟺   x == b / a
a / x == b   ⟺   x == a / b            x / a == b   ⟺   x == b * a
如果您只有一个变量并且已解析所有常量表达式，则您的x将是变量或运算符节点； a将是一个常数。

（（但要小心除法：在上面的示例中，除法没有余数。如果除法有余数，则整数除法在解析x的值时将不会给出正确的结果，并且可能会引入浮点除法小错误。）