构建二进制表达式树

Question

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

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

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

Answer 1

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

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

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

Answer 2

你将需要：

1. 定义描述语言
2. 写一个词法分析器，从您的字符串
3. 写入读取的标记语法从令牌构建树的解析器

例如，看看这个方法：http://en.wikipedia.org/wiki/Recursive_descent_parser

还有其他

Answer 3

转换缀以后缀或前缀

后缀输入为：AB + CDE + **

1. 考虑第一个字符，如果它不是符号然后创建节点将它添加到堆栈
2. 如果字符cter是符号，然后使用符号弹出元素创建节点并将其添加到符号的左侧和右侧
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 4

它可以分为两个步骤：

1. 计算每个令牌的优先级值。

   例如： '+'：1， 'X' 2，数：INF， '（'：添加10至基部， '）'：从基部减去10）的基础上

2. 生成Cartesian tree优先使用堆栈（约5行代码）

您可以在一次扫描中完成。