我得到2 y 5 1 4 3 - * - * +，并被要求评估它，然后绘制等效的表达式树。我以前没有做过任何工作，有人可以展示你解决这类问题的步骤吗？
我看过：公式的后顺序遍历， 并且对如何得出该答案感到困惑。
问问题
498 次
3 回答
1
你得到的是一个后缀表达式。众所周知，这些东西是根据以下规则用堆栈评估的：
从左到右工作，当你遇到一个值时，推动它。遇到运算符时，弹出前两个值，应用运算，然后将结果推回。
所以你的表达式评估是这样进行的
2 (push 2)
2 y (push y)
2 y 5 (push 5)
2 y 5 1 (push 1)
2 y 5 1 4 (push 4)
2 y 5 1 4 3 (push 3)
2 y 5 1 1 (pop 3, pop 4, push 4-3)
2 y 5 1 (pop 1, pop 1, push 1*1)
2 y 4 (pop 1, pop 5, push 5-1)
2 4y (pop 4, pop y, push y*4)
2+4y (pop 4y, pop 2, push 2+4y)
你的答案是留在堆栈上的值。
现在，您还询问了生产一棵树的问题。要生成一棵树，而不是在找到运算符时评估表达式，您可以通过构建一个以运算符为根、弹出的树片段为子项的树片段来“应用”该运算符。
所以推后
2 y 5 1 4 3
你看到 a -，所以你弹出 4 和 3 然后你推回这个结构
-
/ \
4 3
接下来你会看到，*所以你弹出顶部的树片段和它下面的那个，它实际上是一个由单个节点组成的树片段
1
所以它看起来像
*
/ \
1 -
/ \
4 3
你应该可以从这里拿走它。
于 2013-08-03T19:03:12.103 回答
1
正如您链接的问题中 novalis 所述，扫描第一个运算符和前 2 个操作数，然后用括号中更熟悉的表达式替换该组，即。
如果你有：
op1 op2 operator
4 3 -
这变成：
(op1 operator op2)
(4 - 3 )
所以，继续……
2 y 5 1 4 3 - * - * +
2 y 5 1 (4 - 3) * - * +
2 y 5 (1 * (4 - 3)) - * +
以类似的方式继续构建树。扫描第一个运算符并创建一棵小树：
-
/ \
4 3
然后，每个新操作数都是新树的顶部节点：
*
/ \
1 -
/ \
4 3
接着：
-
/ \
5 *
/ \
1 -
/ \
4 3
于 2013-08-03T19:20:46.537 回答
1
Post order traversal of a formula的答案是找到第一个运算符。在您的情况下，它是“-”。他描述的第二步是把它放在前两个操作数之间。在您的情况下，这两个操作数是 4 和 3（它们直接位于“-”之前）。所以这一步之后的公式就变成了：
2 y 5 1 (4-3) * - * +
请记住，表达式 (4-3) 现在是一个操作数。
我们再次将这些步骤应用于此公式。我们看到现在第一个运算符是' '。' ' 前面的两个操作数是 1 和 (4-3)。公式变为：
2 y 5 (1*(4-3)) - * +
现在您可以应用它，直到所有运算符都消失为止。
我不会继续给出更多步骤，因为这可能是一个家庭作业问题。但是我认为这很清楚吗？
于 2013-08-03T18:55:56.623 回答