从后缀表达式评估变量

Question

我正在尝试为单变量方程构建求解器。我正在使用调车场算法，根据 and rici 的建议进行了扩展。显然，该算法非常适合通过给定的数学表达式解析槽，确定其有效性并评估值。但是，我很难理解如何合并求解某个变量。

如果我使用等式 2 * (x - 4) = 4，这可以毫不费力地转换为 RPN 2 x 4 - * 4 -。从这里，很容易评估任何给定 x 的值。但是，如何确定x呢？我正在查看 gab's 答案，虽然我很清楚如何从 RPN 形式构建树，但我不明白如何计算值（他的答案中的第 5 步）。

谢谢。

Answer 1

如果你用铅笔和纸解决这个问题，你会怎么做：你将东西移到等式的另一边，直到只剩下 x。你的树看起来像这样：

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

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

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

to the tree: 删除左边的乘法并在右边插入它的逆运算，除以常数 2。你的树现在看起来像这样：

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

除法对两个常数进行运算。你可以 "fold" 他们进入结果， 2:

（如果您只有一个变量，您可以在创建节点时执行此操作，这样您就没有要删除的 ÷ 节点的中间步骤。你还应在此处检测任何被零除。）

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

计算右边的常量表达式得到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 和 floating- 的值时将不会给出正确的结果点划分可能会引入小错误。）

从后缀表达式评估变量

Evaluating variable from postfix expression

c++

algorithm

math

postfix-notation

shunting-yard