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 回答