构建二进制表达式树

Question

有人可以解释如何构建二进制表达式树.

例如,我有一个字符串2*(1+(2*1));如何将其转换为二进制表达式树.

 *
 | \
 |  \
 2  +
    |\
    1 *
      |\
      2 1

Answer 1

将中缀转换为后缀或前缀

后缀输入为:ab + cde +**

1. 如果它不是符号,则考虑第一个字符然后创建节点将其添加到堆栈
2. 如果character是symbol,则使用符号pop元素创建节点,并添加到符号的左侧和右侧
3. 将符号节点推入堆栈.
4. 重复1,2和3,直到迭代器没有更多元素

Java实现

public Tree.TreeNode createExpressionTree(){
    Iterator<Character>itr = postOrder.iterator();
    Tree tree = new Tree();
    NodeStack nodeStack = new NodeStack();
    Tree.TreeNode node;
    while (itr.hasNext()) {
        Character c = itr.next();
        if(!isDigit(c)){
            node = tree.createNode(c);
            node.right = nodeStack.pop();
            node.left = nodeStack.pop();
            nodeStack.push(node);
        }else{
            node = tree.creteNode(c);
            nodeStack.push(node);
        }
    }
    node = nodeStack.pop();
    return node;
}

更多信息:http://en.wikipedia.org/wiki/Binary_expression_tree

Answer 2

将表达式转换为前缀或后缀表示法。从那里开始应该非常简单。以下 wiki 链接中提到了算法。

http://en.wikipedia.org/wiki/Polish_notation

http://en.wikipedia.org/wiki/Reverse_Polish_notation