Come memorizzare l'espressione matematica nella lista c ++

5

Sto analizzando un'espressione matematica infissa in un modulo postfix. Voglio memorizzarlo in una lista come [4.5, 3, 0.25, +, -] in modo che possa elaborarlo una volta che è stato analizzato. Potrei riporlo nuovamente in una stringa, ma dovrei analizzarlo due volte. Il problema è che non so come memorizzare operatori e operandi nella stessa lista . Ho pensato a due classi di bambini di un genitore comune, ma sono totalmente diversi.

Qual è il modo migliore per raggiungere questo obiettivo?

    
posta germanfr 10.06.2016 - 22:42
fonte

5 risposte

2

The problem is that I don't know how to store operators and operands in the same list

Considera il pattern di progettazione composito :

L'articolocontinuaamostrareunesempiodiespressionematematica:

Questotipermettedicostruireiltuoalbero.Selodesideri,puoianchearchiviaretuttiglielementiinunalista,madoThis()utilizzal'alberoperattraversare.

Ciòchepotrebbeessereunpo'confusoèchemostratutteleoperazionicomemetodi.Inveceèpossibilememorizzarel'operazionenelnodocomposito.RinominadoThis()incalculate()eorapuoichiamareroot.calculate()percalcolarel'interaespressione.Sarestiingradodifarlosuqualsiasinodo.Avreil'interfacciasimileaquesta:

<<interface>>Component---------+calculate()+getPrefixString()+getInfixString()+getPostfixString()+addElement(Componentcomponent)

Nientedituttoquestotiportaadoverripubblicareglielementimentrevisitiognunodiessi.Eccounmodoperevitarlo:

Orapuoifaretutteleanalisiinanticipoprimadicostruirel'albero.doThis()ocalculate()comelorinominerei,saqualeoperatoreusarepolimorficamente.

Datochetuttihannolostessotipo,Component,seiliberodimemorizzarliinunelenco,arrayoaltro.Mailmodoincuisicolleganoèancoraunalbero.

Haiespressounproblemadicostruzionerelativoallanotazioneinfisso.Considera il modello di build . È buono per la costruzione di materiali compositi. Il link che ho fornito ti porta attraverso il refactoring solo in questo caso. Penso che troverai abbastanza energia da poter gestire infisso, prefisso e postfix.

    
risposta data 11.06.2016 - 15:45
fonte
0

How to store math expression in c++ list

Considera gli alberi

La cosa fondamentale qui è che le notazioni prefisso, infisso e suffisso sono solo modi di presentare espressioni matematiche. Quando ti riponi non devi preoccuparti di come sono stati presentati. La cosa interessante di tree's è che puoi tradurre espressioni equivalenti in queste notazioni in albero identico. E puoi convertire l'albero in una di queste notazioni.

Ecco lo stesso albero, attraversato allo stesso modo ogni volta. La differenza è quando si prende il valore dal nodo. La differenza è il punto. Quando tocchi il punto raccogli (o posi) la lettera. Ruotando il punto si ottengono i caratteri nelle tre diverse notazioni.


Prefisso:attraversamentopre-ordine


Infix:traversalin-order


Postfix:postordertraversal

C'èunastrutturadatic++chefunzionabeneperquesto.Sichiama btrees

    
risposta data 11.06.2016 - 06:48
fonte
0

Mentre penso che la risposta di CandiedOrange sia un approccio migliore dato che gli alberi sono molto più utili per eseguire operazioni sulle espressioni, se tutto ciò che si vuole fare è archiviarlo e poi valutarlo, un elenco postfix e un valutatore stack-based è adeguato e più semplice.

Quando dici che non c'è niente in comune tra operandi e operatori, non è del tutto vero. Per eseguire la tua espressione, dovrai visitare ciascuno di essi in ordine, fornendo uno stack con cui lavorare. Gli operatori spingeranno un valore in pila, mentre gli operatori faranno scoppiare una coppia di valori, eseguire un calcolo e premere il risultato. Entrambi possono avere la stessa interfaccia: sono operazioni stack .

    
risposta data 11.06.2016 - 13:39
fonte
0

(Presumo e spero che tu voglia inserire il codice genuino C ++ 11 o C ++ 14 utilizzando il suo standard contenitori & utilità libreria ; non utilizzare una precedente variante di C ++, assicurati di avere un compilatore recente : a giugno 2016, usa GCC versione 5 o 6 e / o Clang / LLVM versione 3.7 o 3.8 , essendo entrambi software gratuito )

Probabilmente vuoi rappresentare l' albero di sintassi astratto (AST) delle tue espressioni analizzate. Ulteriori informazioni su analisi . Potresti voler leggere i primi capitoli del Libro dei draghi . Oppure codifica un semplice parser di discesa ricorsivo . Oppure usa un parser generator (spesso erroneamente chiamato compilatore-compilatore ) come ANTLR3 o GNU bison -o alcuni yacc -). BTW il tuo problema è simile a uno degli esempi forniti in bison documentazione ( infix calc ).

Non organizzerai il tuo AST come un elenco in C ++, ma come un albero . Ad esempio, potresti avere una superclasse comune (astratta) class expr e avere una sottoclasse astratta per foglie class leaf_expr: public class expr con sottoclassi finali concrete come class int_expr: public leaf_expr per valori letterali interi (ad esempio 12 ), class var_expr: public leaf_expr per variabili (ad es. %codice%). Avrai una superclasse x per i nodi binari contenenti puntatore intelligente (probabilmente class binary_expr : class_expr ...) per sottoalberi sinistro e destro- con sottoclassi finali in calcestruzzo std::shared_ptr<expr> ecc per i nodi somma (ad esempio per class sum_expr : public class binary_expr ).

Se hai bisogno di ottenere una traduzione postfissa del tuo AST, definirai un'altra rappresentazione per le espressioni postfisse, forse come una lista di puntatori intelligenti ai componenti postfix, e definirai un'altra gerarchia di classi per i tuoi componenti postfix: una superclasse astratta x+12 con varie sottoclassi class postfix (per un operando letterale intero postfisso come class int_postfix ), 12 (per un operando variabile postfisso come class var_postfix ), x (per un operatore postfisso come class plus_postfix ), usando alcune superclassi astratte intermedie come + per operandi e class operand_postfix : public postfix e probabilmente class operator_postfix : public postfix e class unary_operator_postfix : public operator_postfix ecc ...) ... e hanno una lista di puntatori intelligenti di questi ( per esempio class binary_operator_postfix : public operator_postfix ...). Quindi puoi facilmente codificare un trasformatore da AST a elenco postfix:

std::list<std::unique_ptr<postfix>> transform_ast_to_postfix
    (std::shared_ptr<expr>);

The problem is that I don't know how to store operators and operands in the same list

Avrai una lista di puntatori intelligenti per una super classe comune, ad es. %codice%. In alcuni casi (ma non nel tuo) potresti anche considerare di avere un elenco di oggetti contenenti una unione taggata . FWIW C ++ 17 ti darà std :: qualsiasi

(Si potrebbe evitare esplicitamente che rappresenta AST in memoria e costruire direttamente l'elenco di puntatori intelligenti su std::list<std::unique_ptr<postfix>> elementi nelle azioni del parser, ma credo che la costruzione dell'AST sia più facile e più generale)

Si noti che una buona comprensione dei puntatori e puntatori intelligenti è essenziale . L'utilizzo di puntatori intelligenti invece di puntatori non elaborati (ad esempio std::list<std::unique_ptr<postfix>> ) potrebbe aiutarti a scrivere codice più pulito ed evitare perdite di memoria . Dovresti capire RAII e probabilmente (in C ++ 11) regola di cinque . Vedi questa domanda.

Dovresti leggere la programmazione - Principi e ampli di Stroustrup; pratica usando C ++

    
risposta data 12.06.2016 - 08:24
fonte
-1

Se l'espressione è già convertita in RPN / postfix, hai solo bisogno di un vettore o array di base. Crea una semplice struttura dati che contenga sia i valori che le informazioni dell'operatore e spinga ogni elemento nell'elenco.

struct myToken {
   int tokType;  //1 = value, 2 = operator
   float tokVal;
   int opType; //1 = add, 2 = sub, 3 = mult, etc
}

Per rivalutare l'espressione basta ripetere l'elenco. Puoi anche estenderlo per supportare chiamate di funzioni come sum () sqrt () aggiungendo membri per tenere traccia di un nome di funzione e il numero di parametri richiesti, e facendoti controllare dal tuo valutatore di espressioni.

    
risposta data 12.06.2016 - 09:20
fonte

Leggi altre domande sui tag