Precisione di parentesi graffe

Question

Sono molto nuovo a java e sto costruendo una calcolatrice, che accetta un'equazione e la valuta.

Sto utilizzando il metodo Scanner per ottenere un input, ma ciò significa che il mio input è di tipo Scanner. Cosa dovrei fare per questo input in modo da poterlo valutare? E una volta che posso valutarlo, come posso dare precedenza alle parentesi?

Ad esempio, per l'equazione (5 * (4 + 3)) * 2, mi piacerebbe che il programma valutasse (4 + 3) prima, quindi lo abbia moltiplicato per 4, quindi tutto ciò moltiplicato per 2.

Grazie mille.

Answer 1

Penso che questo sarà utile: Polish notation e Reverse Polish notation. Spiegano l'idea di come dividere la stringa in un albero ed eseguire un passo alla volta.

Answer 2

Quello che ti serve è Dijkstra's Shunting Yard Algorithm. Ciò converte la notazione matematica in-fix in notazione post-fix, che ordina ordinatamente tutti i problemi con la precedenza e le parentesi degli operatori in quanto la notazione post-fix non ha bisogno di nessuno dei due. La pagina di Wikipedia ha un esempio completo in C, che potrebbe essere tradotto in Java.

Answer 3

@Il suggerimento di Simon G di suggerimento sull'uso dell'algoritmo Shunting Yard di Dijkstra lo ha inchiodato. È necessario implementare la "micro-grammatica" per analizzare i simboli, ma Scanner può eseguire il 95% del lavoro.

Un'alternativa sarebbe implementare il parser di espressioni utilizzando un generatore di parser come ANTLR o Javacc e quindi implementare la valutazione come un attraversamento dell'albero. Ma è piuttosto pesante se vuoi semplicemente valutare l'espressione una volta.

Infine, voglio sottolineare che anche se questo è un problema ben noto (risolto), non è banale ... in nessuna lingua. E forse questo ti sta dicendo che devi fare ancora un po 'di lettura su algoritmi e/o compilatori per completare le tue conoscenze.