公式的后序遍历
在数据结构中，我将按顺序转换和预排序公式转换为树。不过，我不太擅长后期订购。
对于给定的公式 xyz + ab - c * / -
我想出了
<前><代码> - /\ * /（除） / \ / \ x + - c / \ /\ 伊扎布
在大多数情况下，这似乎很合适，除了左子树中的 * 是牌组中的小丑。在后序遍历中，最后一个字符是树的顶部节点，其他所有节点都向下分支。现在我使用 / 和 * 运算符来表示它们应该位于相反的节点上。然而，当遍历树时，除了 * 之外的所有内容都适合，因为左子树必须向上移动到根之前的节点，然后切换到右子树。
朝着正确方向的推动值得赞赏。
In data structures, I get converting in order and pre-order formula conversions into trees. However, I'm not so good with post-order.
For the given formula x y z + a b - c * / -
I came up with
- / \ * / (divide) / \ / \ x + - c / \ /\ y z a b
For the most part, this seems to fit, except the * in the left subtree is the joker in the deck. In post order traversal, the last character is the top node of the tree, everything else branches down. Now I take the / and * operators to mean that they should be on opposing nodes. However, when traversing tree, everything fits except for the *, since the left subtree has to work up to the node prior to the root, then switch over to the right subtree.
A nudge in the right direction is appreciated.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
按顺序走。首先，再次写出整个堆栈：
xyz + ab - c * / -
现在，从左侧开始，查找第一个运算符。将它和堆栈中的前两个操作数替换为一点有序位：
x (y + z) ab - c * / -
继续下一个运算符：
x (y + z) (a - b ) c * / -
然后下一个：
x (y + z) ((a - b) * c) / -
x ((y + z) / ((a - b) * c)) -
x - ((y + z) / ((a - b) * c))
现在，要使其成为一棵树，只需从中间开始（您已经知道它是原始堆栈中的最后一个元素），并从中挂起带括号的子表达式，从外到内。
Go in order. First, write out the entire stack again:
x y z + a b - c * / -
Now, starting at the left, look for the first operator. Replace it and the previous two operands, right there in the stack, with a little in-order bit:
x (y + z) a b - c * / -
Continue with the next operator:
x (y + z) (a - b) c * / -
Then the next:
x (y + z) ((a - b) * c) / -
x ((y + z) / ((a - b) * c)) -
x - ((y + z) / ((a - b) * c))
Now, to make it a tree, just start at the middle (which you already know as it's the last element in the original stack), and hang parenthesized subexpressions from it, outside-to-inside.
实际上，编写一个解析后序表达式的程序比编写一个按顺序解析它的程序更容易，因为您不必检查操作的优先级。
试试这个：创建一个堆栈，然后将找到的操作数添加到其中（从左到右）。当找到一个操作时，从堆栈中提取它期望的操作数数量并放回一棵小树。完成后，堆栈中将只有一个结果：最终图表。
前任：
Actually, it's easier to write a program that parses a post-order expression than one that parses it in-order, because you don't have to check the priorities of operations.
Try this: make a stack, and add to it the operands as you find them (left to right). When you find an operation, extract the number of operands it expects from the stack and put back a small tree. When you finish it, you'll have only one result in the stack : the final graph.
Ex: