Как поместить постфиксные выражения в двоичное дерево?

Question

так что у меня есть двоичное дерево и постфиксное выражение "6 2 * 3 /", какой алгоритм поместить его в дерево?как,

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

Answer 1

Чтобы построить дерево из выражения, представьте, что вы оцениваете его напрямую, но строите деревья вместо вычисления чисел.(Этот прием работает гораздо больше, чем выражения с постфиксным кодом.)

Алгоритм: Имеет стек для хранения промежуточных значений (которые являются деревьями) и проверяет каждый токен слева направо:

• Если это число, превратите его в листовой узел и поместите в стек.
• Если это оператор, вытолкните два элемента из стека, создайте узел операторас этими потомками и поместите новый узел в стек.

В конце, если выражение сформировано правильно, в стеке должно быть ровно одно дерево, которое является полным выражением в деревеформа.

Answer 2

Postfix-to-tree(j){
  n <--ALLOCATE_NODE(A[j],NULL,NULL)
    Switch
      case Postfix[j] is a binary operator
        do j <--j-1
         right[n] <-- Postfix-to-tree(j)
              j <-- j-1
              left[n] <--postfix-to-tree(j)
                 case postfix[j] is a unary operator 
               do j <-- j-1
                  right[n] <-- Postfix-to-tree(j)
}