如何将后缀表达式放在二叉树中？

Question

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

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

Answer 1

要从表达式构造树,假装您直接评估它,但构造树而不是计算数字.(这个技巧比后缀表达更多的东西.)

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

• 如果是数字,请将其转换为叶节点并将其推入堆栈.
• 如果是运算符,则从堆栈中弹出两个项目,构造一个包含这些子节点的运算符节点,然后在堆栈上推送新节点.

最后,如果表达式正确形成,那么您应该在堆栈上只有一棵树,它是树形式的整个表达式.