从代数表达式创建二叉树

我必须用Java创建算术评估器。为此，我必须解析二叉树中的代数表达式，然后计算并返回结果。因此，第一步如何解析二叉树中的表达式？我知道这个理论，但我的概率是如何在Java中做到这一点。我读了以下帖子 create recursive binary tree 从代数表达式创建二叉树

但我错过了基本的技巧或方法。我知道如何创建一个节点（我有一个类的方法，如returnNodeValue，isLeaf，isDoubleNode，isSingleNode等），但我想我需要一个方法在二叉树中插入一个节点，以达到我想要的效果。有任何想法吗？

来源

2011-10-23 Anila

你到目前为止尝试过什么？伪代码在那里（并且网上有很多实现，无论好坏）。 –

我已经写了函数来读取后缀，中缀和前缀顺序的树。我知道有很多例子，但是我找不到我要找的东西。我需要从如何从代数表达式（我的意思是如何表达和测试优先级并存储值等）开始创建一棵树。我知道我要求的是基本的，但我只是卡住了。任何链接或帮助将不胜感激。谢谢。 – Anila

一般来说，要编写一个解析器，你需要一个语法。然后有很多种解析器。在网上搜索“递归下降”解析器 - 很容易理解如何对它们进行编码。顺便问一下，这是功课吗？ –

树建设前缀表达式

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

应用（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 = ?

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

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

鉴于从前缀表达式构建树的简单，我建议使用标准stack algorithm转换从缀到前缀。在实践中，您会使用堆栈算法来评估中缀表达式。

来源

2011-10-23 15:33:31 blackcompe

终于找到了感谢你的所有步骤。从中缀转换为前缀（参见[Shunting-yard算法]（https://en.wikipedia.org/wiki/Shunting-yard_algorithm）：比提供的链接更好地解释） - >创建树 - >使用反向后处理命令遍历。谢谢！ – Fitz

_如果树是空的，则表达式中的第一个标记（必须是是一个运算符）_除非整个表达式包含一个操作数。 – Fitz

我想你可能会有点困惑你应该做的：

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

你所说的二叉树实际上是一个分析树，它不是严格的二叉树（因为不是所有的树节点都是二叉树）。（除了“二叉树”有二进制搜索树的内涵，这不是你在这里需要的。）

你已经想通了解析表达式，解析树的构造非常直-前锋。例如：

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); 
     } 
    // ... 
}

注：这是行不通的代码...这是一个提示，以帮助你做你的功课。

来源

2011-10-23 14:39:02

从代数表达式创建二叉树

回答

相关问题