Crear árbol de expresiones binarias

Question

¿Podría alguien explicar cómo construir un árbol de expresiones binarias?

Por ejemplo, tengo una cadena 2*(1+(2*1)); Cómo convertir esto en un árbol de expresiones binarias.

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

Answer 1

Convierte la expresión de prefijo o notación de sufijo. A partir de ahí, debería ser bastante sencillo. Los algoritmos se mencionan en los siguientes enlaces de la wiki.

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

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

Answer 2

tendrá que:

1. definir una gramática que describe su idioma
2. escribir un analizador léxico que lee las señales de la cadena de
3. escritura un analizador sintáctico que construye un árbol desde los tokens

por ejemplo, echar un vistazo a este enfoque: http://en.wikipedia.org/wiki/Recursive_descent_parser

hay otros

Answer 3

Convertir infijo a postfix o prefijo

La entrada de sufijo es: AB + cde + **

1. Considera el primer carácter si no es un símbolo, luego crea el nodo agrégalo a la pila
2. If chara cter es un símbolo y luego crea un nodo con elementos pop de símbolos y se agrega a la izquierda y a la derecha del símbolo
3. Inserta el nodo de símbolo en la pila.
4. Repetir 1, 2 y 3 hasta el iterador no tiene más elementos Implementación

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; 
} 

Más información: http://en.wikipedia.org/wiki/Binary_expression_tree

Answer 4

Se puede dividir en dos etapas:

1. Calcule el valor de prioridad para cada token.

   Por ejemplo: '+': 1, 'x': 2, cantidad: inf, '(': añadir 10 a la base, ')': restar 10 de base)

2. Build Cartesian tree basado en prioridad mediante el uso de una pila (aproximadamente 5 líneas de código)

Puede hacerlo en un solo análisis.