Espressioni di scrittura: Infix, Postfix e Prefix

Question

Il mio compito è di scrivere un'app (sfortunatamente su C) che legge l'espressione in notazione infissa (con variabili, operatori unari e binari) e la memorizza in memoria, quindi la valuta. Inoltre, è necessario verificare la correttezza.

ad esempio:

  

3 * (A + B) - (- 2-78) * 2 + (0 * A)

Dopo aver ottenuto tutti i valori, il programma dovrebbe calcolarlo.

La domanda è: Qual è il modo migliore per farlo? (Con ottimizzazione e validazione)

Quale notazione scegliere come base dell'albero?

Devo rappresentare l'espressione come albero? In tal caso, posso ottimizzarlo facilmente (basta rilasciare nodi che restituiscono 0 o smth altro).

Saluti,

Answer 1

Il link suggerito nel commento di Greg Hewgill sopra contiene tutte le informazioni di cui hai bisogno:

Se insisti a scrivere il tuo,

• un parser ricorsivo di discesa è probabilmente il modo più semplice per farlo a mano.
• Altrimenti potresti usare uno strumento come Bison (dato che stai lavorando in C). Questo tutorial è il migliore che abbia mai visto lavorare con Flex e Bison (o Lex / Yacc)

Puoi anche cercare " valutatore di espressioni " su Codeproject - hanno molti articoli sull'argomento.

Mi sono imbattuto nell'analizzatore di espressioni del programma M4 qualche tempo fa. Puoi studiare il suo codice per vedere come funziona. Penso che questo link su Google Codesearch è la versione che ho visto.

Answer 2

La tua domanda suggerisce i requisiti richiesti dalla tua soluzione:

  

sfortunatamente su C

quindi alcuni suggerimenti qui potrebbero non essere ammessi. Tuttavia, suggerirei che questo è un problema piuttosto complicato da risolvere, e che saresti molto meglio cercare di trovare una libreria esistente adatta che potresti collegare nel tuo codice C per fare questo per te . Ciò probabilmente ridurrebbe il tempo e gli sforzi necessari per far funzionare il codice e ridurrebbe gli sforzi di manutenzione in corso. Ovviamente, dovresti pensare alle licenze, ma sarei sorpreso se non ci fosse una buona libreria di analisi / valutazione "disponibile". che potrebbe fare un buon lavoro.