2

在数据结构中，我将按顺序转换和预排序公式转换为树。但是，我对后订购不是很好。

对于给定的公式x y z + a b - c * / -

我想出了

                   -
                 /   \
                *     / (divide)
               / \    / \   
              x  +    -  c
                / \  /\
               y  z a  b

在大多数情况下，这似乎很合适，除了左子树中的 * 是甲板上的小丑。在后序遍历中，最后一个字符是树的顶部节点，其他所有内容都向下分支。现在我将 / 和 * 运算符表示它们应该位于相反的节点上。但是，在遍历树时，除了 * 之外的所有内容都适合，因为左子树必须先到达根节点之前的节点，然后再切换到右子树。

向正确方向轻推是值得赞赏的。

4

2 回答 2

3

按顺序走。首先，再次写出整个堆栈：

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))

现在，要使它成为一棵树，只需从中间开始（您已经知道它是原始堆栈中的最后一个元素），然后从外到内悬挂带括号的子表达式。

于 2010-10-14T02:02:29.790 回答
0

实际上，编写一个解析后序表达式的程序比按顺序解析它更容易，因为您不必检查操作的优先级。

试试这个：创建一个堆栈，并在找到操作数时将其添加到其中（从左到右）。当你找到一个操作时，从堆栈中提取它期望的操作数的数量并放回一棵小树。完成后，堆栈中只有一个结果：最终图。

前任：

x y z +  ->  x   +
               /  \
              y    z
于 2010-10-14T01:47:17.840 回答