后序遍历公式
我得到了2 y 5 1 4 3 - * - * +，并被要求对它进行评估，然后绘制等价的表达式树。我以前没有做过任何这方面的工作，有人能给出你解决这类问题的步骤吗？
我看过：Post order traversal of a formula，我不知道该怎么回答这个问题。
回答 3
Stack Overflow用户
发布于 2013-08-03 19:03:12
给你的是一个后缀表达式。众所周知，这些东西是按照以下规则用堆栈来评估的：
从左到右工作，当你遇到一个值时，推它。当您遇到一个操作符时，弹出前两个值，应用该操作，并将结果推回。
所以你的表达式评估是这样进行的
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你看到一个-，所以你弹出4和3，然后把这个结构向后推
-
/ \
4 3接下来，您将看到*，因此您将弹出顶部和下面的树片段，这实际上是一个由单个节点组成的树片段。
1所以看起来就像
*
/ \
1 -
/ \
4 3你应该可以从这里拿走它。
Stack Overflow用户
发布于 2013-08-03 18:55:56
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)) - * +现在你可以应用这个，直到所有的操作符都消失了。
我不会继续给出更多的步骤，因为这可能是一个家庭作业问题。不过，我认为这是清楚的？
Stack Overflow用户
发布于 2013-08-03 19:20:46
正如novalis从您链接的问题中指出的，扫描第一个操作符和前两个操作数，然后用括号中更熟悉的表达式替换该组，即。
如果你有：
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 3https://stackoverflow.com/questions/18036051
复制相似问题
腾讯云开发者
