algorithm - 如何将后缀表达式放入二叉树中？

Question

所以我有一个二叉树和一个后缀表达式“6 2 * 3/” 把它放在树上的算法是什么？ 喜欢，

          [/]
          / \
        [*]  [3]
        / \
      [6] [2]

Answer 1

要从表达式构造一棵树，假设您正在直接评估它，但构造树而不是计算数字。 (这个技巧适用于比后缀表达式更多的东西。)

算法:有一个堆栈来存储中间值(树)，并从左到右检查每个标记:

• 如果是数字，则转为叶子节点入栈。
• 如果它是一个运算符，从堆栈中弹出两个项目，用这些 child 构造一个运算符节点，并将新节点压入堆栈。

最后，如果表达式的格式正确，那么堆栈中应该只有一棵树，它是树形式的整个表达式。