从代数表达式创建二叉树

Question

我必须用 Java 创建一个算术计算器。为此，我必须解析二叉树中的代数表达式，然后计算并返回结果。那么第一步如何解析二叉树中的表达式？我知道这个理论，但我的问题是如何在 Java 中做到这一点。我读了下面的帖子 创建递归二叉树

但是我缺少基本的技巧或方法。我知道如何创建一个节点（我有一个类，其中包含 returnNodeValue、isLeaf、isDoubleNode、isSingleNode 等方法），但我认为我需要一个方法来在二叉树中插入节点来实现我想要的。有什么想法吗？

Answer 1

前缀表达式的树结构

def insert

     Insert each token in the expression from left to right:

     (0) If the tree is empty, the first token in the expression (must
         be an operator) becomes the root

     (1) Else if the last inserted token is an
         operator, then insert the token as the left child of the last inserted
         node.

     (2) Else if the last inserted token is an operand, backtrack up the
         tree starting from the last inserted node and find the first node with a NULL
         right child, insert the token there. **Note**: don't insert into the last inserted 
         node. 
end def

让我们做一个例子：+ 2 + 1 1

Apply (0)。

  +

应用（1）。

  +
 /
2 

应用（2）。

  +
 / \
2   +

应用（1）。

  +
 / \
2   +
   /
  1 

最后，应用(2)。

  +
 / \
2   +
   / \
  1   1

该算法已针对 - * / 15 - 7 + 1 1 3 + 2 + 1 1 进行了测试，

因此 Tree.insert 实现就是这三个规则。

insert(rootNode, token)
  //create new node with token
  if (isLastTokenOperator)//case 1
      //insert into last inserted's left child
  else {                  //case 2
      //backtrack: get node with NULL right child
      //insert
  }
  //maintain state
  lastInsertedNode = ?, isLastTokenOperator = ?

评估树有点有趣，因为你必须从树的右下角开始。执行反向后序遍历。首先拜访正确的孩子。

evalPostorder(node)
  if (node == null) then return 0
  int rightVal = evalPostorder(node.right)
  int leftVal = evalPostorder(node.left)
  if(isOperator(node.value)) 
       return rightVal <operator> leftVal    
  else
       return node.value

鉴于从前缀表达式构造树的简单性，我建议使用标准的堆栈算法从中缀转换为前缀。在实践中，您可以使用堆栈算法来计算中缀表达式。

Answer 2

我认为您可能对自己应该做什么感到有点困惑：

...但我想我需要一种在二叉树中插入节点的方法...

您所说的二叉树实际上是一个解析树，并且它不是严格意义上的二叉树（因为并非所有树节点是二进制的）。 （除了“二叉树”具有二叉搜索树的含义，而这根本不是您在这里需要的。）

您已经弄清楚如何解析表达式，解析树的构造非常漂亮直截了当。例如：

Tree parseExpression() {
    // ....
    // binary expression case:
        Tree left = parseExpression();
        // parse operator
        Tree right = parseExpression();
        // lookahead to next operator
        if (...) {
        } else {
            return new BinaryNode(operator, left, right);
        }
     // ...
}

---

注意：这不是工作代码...这是帮助您做作业的提示。