Conversión de una expresión infija (con paréntesis) en un árbol binario

Question

Como parte de una asignación Java, tengo que tomar una expresión aritmética de entrada y almacenarla en un árbol binario.

He hecho todo lo necesario para la tarea, excepto la parte donde leo en la cadena de la expresión y la almaceno en el árbol binario.

He creado una clase llamada BinaryTree. Su único campo es un treenode llamado raíz. Este treenode se define como una clase interna en BinaryTree. Tiene 3 campos, un campo de datos genérico y dos secundarios (izquierdo y derecho) que son de tipo BinaryTree.

Estoy teniendo un momento muy difícil definir un algoritmo para la lectura en una expresión como

(5 * (2 + 3)^3)/2

y almacenarla en un árbol como

  /
     ^  2 
    *  3 
    5 + 
    2 3 

¿Alguien puede ayudar con el algoritmo?

Answer 1

Eche un vistazo a shunting-yard algorithm. De Wikipedia:

En informática, el algoritmo de yarda de derivación es un método para analizar expresiones matemáticas especificadas en notación infija. Se puede usar para generar resultados en notación polaca inversa (RPN) o como un árbol de sintaxis abstracta (AST). El algoritmo fue inventado por Edsger Dijkstra y se lo denominó el algoritmo "patio de maniobras" porque su funcionamiento se asemeja al de un patio de maniobras ferroviarias. Dijkstra describió por primera vez el Algoritmo de yarda de maniobras en el informe Mathematisch Centrum MR 34/61.

Answer 2

Aquí hay algunos C++ code to create a binary expression tree que utilizan dos pilas, una para los operadores y otra para los operandos. Eventualmente, la pila de operandos contiene un elemento, el árbol de expresiones binarias completo.