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

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. если в стеке есть какой-либо оператор, перейдите к левой ветви вашего узла и вызовите свой алгоритм, затем перейдите к правой ветви и вызовите свой алгоритм.

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