Conversione di un'espressione infissa (con parentesi) in un albero binario

Question

Come parte di un compito Java, devo prendere un'espressione aritmetica di input e archiviarla in un albero binario.

Ho eseguito tutto il necessario per l'assegnazione tranne la parte in cui ho letto la stringa dell'espressione e la memorizzo nell'albero binario.

Ho creato una classe chiamata BinaryTree. Il suo unico campo è un treenode chiamato root. Questo treenode è definito come un innerclass in BinaryTree. Dispone di 3 campi, un campo dati generici e due figli (sinistro e destro) di tipo BinaryTree.

sto avendo un tempo molto difficile definire un algoritmo per la lettura in un'espressione come

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

e riporlo in un albero come questo

  /
     ^  2 
    *  3 
    5 + 
    2 3 

Qualcuno può aiutare con l'algoritmo?

Answer 1

Dai uno sguardo allo shunting-yard algorithm. Da Wikipedia:

In informatica, l'algoritmo di shunting-yard è un metodo per l'analisi delle espressioni matematiche specificato nella notazione infisso. Può essere utilizzato per produrre output in notazione polacca inversa (RPN) o come albero sintassi astratto (AST). L'algoritmo è stato inventato da Edsger Dijkstra e denominato algoritmo "shunting yard" perché la sua operazione assomiglia a quella di un cantiere di smistamento ferroviario. Dijkstra descrisse per la prima volta l'Algoritmo dello Shunting Yard nel rapporto Mathematisch Centrum MR 34/61.

Answer 2

Ecco alcuni C++ code to create a binary expression tree che utilizza due stack, uno per gli operatori e un altro per gli operandi. Alla fine, lo stack degli operandi contiene un elemento, l'albero di espressioni binarie completo.