Создать рекурсивное двоичное дерево?

Question

У меня есть два стека, один с операндами, другой с операторами. Моя проблема заключается в том, чтобы превратить эти два стека в двоичное дерево.

Например, выражение (2+3)*(4-3) будет переведен в постфикс (такой, что 24+43-*), а затем положить в два стека3442 а также *-+ будут стеки (с вершинами 3 и * соответственно).

Теперь с этими стеками мне нужно сформировать двоичное дерево, как

   *
 +    -
2 3  4 3

Есть ли способ сделать это рекурсивно?

Прямо сейчас у меня есть такой алгоритм:

• Создайте корень дерева, назначьте значение корня первому оператору в стеке операторов. Установите правый и левый указатели на ноль.

• Создайте правый узел, назначьте значение следующего оператора, если он существует, если не назначьте ему операнд. Затем сделайте то же самое для левого узла.

Моя проблема в том, чтобы сделать это рекурсивным или заставить его обрабатывать множество различных случаев.

Спасибо за вашу помощь.

Answer 1

При условии, что у вас есть только бинарные операторы

treeNode createNode(operators, operands) {
  // take first operator and create a new treeNode with it. pop it from the operators stack 

  // if it is the last operator in the list then there should be only two operands left in the operands and you can assign them to the left and right child of the treeNode. return this treeNode.

  // if it is not the last operator then split the operands in two stacks equally
  // leftOperands and rightOperands
  // left child becomes createNode(operators, leftoperands)
  // right child becomes createNode(operators, rightoperands)
  // return this treeNode

}

Answer 2

Рекурсивный алгоритм:

• найти оператора наивысшего приоритета
• разделить выражение вокруг этого оператора
• рекурсивно применить к обеим частям

Answer 3

В общем, нет способа сделать это. Означает ли "1 2 3 4" "* + /" "1 2 3 4 * + /" (то есть "1 / (2 + 3 * 4)") или "1 2 * 3 + 4 /", (то есть "(1 * 2 + 3) / 4").

Answer 4

Если ваше выражение всегда симметрично (одинаковое количество операндов и операторов на каждой стороне оператора), то метод, который вы описываете, работает нормально, с небольшой модификацией:

1. создать узел, назначить значение верхнего оператора в стеке операторов.
2. если в стеке операторов не осталось операторов, извлеките 2 операнда из стека операндов и назначьте их левой и правой ветви, затем выйдите
3. если в стеке есть какой-либо оператор, перейдите к левой ветви вашего узла и вызовите свой алгоритм, затем перейдите к правой ветви и вызовите свой алгоритм.

(Ян объяснил это намного яснее в своем ответе...)