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

Question

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

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

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

* 
+ - 
2 3 4 3 

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

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

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

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

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

Благодарим за помощь.

Answer 1

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

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

Answer 2

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

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 3

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

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

(Ян объяснил это так гораздо понятнее в своем ответе ...)

Answer 4

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