algorithm - 构建二叉表达式树

Question

谁能解释一下如何构建二叉表达式树。

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

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

Answer 1

将中缀转换为后缀或前缀

后缀输入为:a b + c d e +**

1. 如果不是符号则考虑第一个字符然后创建节点将其添加到堆栈
2. 如果字符是symbol则用symbol pop元素创建节点并添加到symbol的左右
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