创建递归二叉树？

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. 如果运算符堆栈上没有运算符，则从操作数堆栈中弹出2个操作数并将它们分配给左右分支，然后退出
3. 如果堆栈上有任何运算符，则转到节点的左分支并调用你的算法，然后转到正确的分支并调用你的算法。

（Jan 在他的回答中解释得更清楚......）

Answer 4

一般来说，没有办法做到这一点。 “1 2 3 4”“* + /”是指“1 2 3 4 * + /”（即“1 / (2 + 3 * 4)”）还是“1 2 * 3 + 4 /”，(即“(1 * 2 + 3) / 4”)。