Come valutare un'espressione nella notazione prefisso

evaluation expression-trees s-expression

Domanda

Sto cercando di valutare un elenco che rappresenta un'espressione in notazione prefisso. Ecco un esempio di un elenco di questo tipo:

[+, [sin, 3], [- 10 5]]

Qual è il modo migliore per valutare il valore della lista

Risposta accettata

Sarà più semplice se hai usato postfix anziché prefisso. Vedi Reverse Polish Notation (RPN) . Data un'espressione in RPN, è facile valutare l'utilizzo di un solo stack.

Ma dal momento che hai chiesto un modo per valutare le espressioni di prefisso senza ricorsione e l'utilizzo di stack (per un modo forse più semplice, vedi EDIT: sotto), ecco un modo:

Possiamo farlo usando due pile.

Uno stack (chiamalo Evaluation) contiene gli operatori (come +, sin etc) e operandi (come 3,4 ecc.) E l'altro stack (chiamalo Count) contiene una tupla del numero di operandi rimasti da vedere + il numero degli operandi che un operatore si aspetta

Ogni volta che vedete un operatore, spingete l'operatore sullo stack di valutazione e spingete la tupla corrispondente sullo stack dei conteggi.

Ogni volta che vedi un operando (come 3,5 ecc.), Controlli la tupla superiore dello stack dei conteggi e diminuisci il numero di operandi rimasti in quella tupla.

Se il numero di operandi rimasti visibili diventa zero, si apre la tupla dalla pila Conteggio. Quindi dallo stack di valutazione compila il numero di operandi richiesti (lo sai a causa dell'altro valore della tupla), spegni l'operatore e fai l'operazione per ottenere un nuovo valore (o operando).

Ora sposta nuovamente il nuovo operando nello stack Valutazione. Questo nuovo operando ti spinge a dare un'altra occhiata in cima allo stack dei Conti e tu fai la stessa cosa che abbiamo appena fatto (decrementare gli operandi visti, confrontare con zero ecc.).

Se il numero dell'operando non diventa zero, si continua con il token successivo nell'input.

Ad esempio, supponi di dover valutare + 3 + 4/20 4

Le pile appariranno (a sinistra è la cima della pila)

Count                  Evaluation                   Input
                                                   + 3 + 4 / 20 4

(2,2)                   +                            3 + 4 / 20 4

(2,1)                   3 +                            + 4 / 20 4

(2,2) (2,1)             + 3 +                            4 / 20 4

(2,1) (2,1)             4 + 3 +                            / 20 4

(2,2) (2,1) (2,1)       / 4 + 3 +                            20 4

(2,1) (2,1) (2,1)       20 / 4 + 3 +                            4

(2,0) (2,1) (2,1)       4 8 / 4 + 3 +                   

Since it has become zero, you pop off two operands, the operator / 
and evaluate and push back 5. You pop off (2,0) from the Count stack.

(2,1) (2,1)                5 4 + 3 +

Pushing back you decrement the current Count stack top.

(2,0) (2,1)               5 4 + 3 + 

Since it has become zero, you pop off 5,4 and + and evaluate and push back 9. 
Also pop off (2,0) from the count stack.

(2,0)                          9 3 + 

                               12

MODIFICARE:

Un amico ha suggerito un modo per farlo senza stack multipli:

Inizia dalla fine, vai al primo operatore. I token alla destra di questo saranno operandi. Valutare e ripetere. Sembra molto più semplice rispetto a farlo con due pile. Possiamo usare una lista doppiamente collegata per rappresentare l'input che cambiamo durante l'elaborazione. Quando si valuta, si eliminano i nodi e quindi si inserisce il risultato. Oppure potresti semplicemente usare una pila.


Risposta popolare

BACIO, valuta al contrario come un'espressione postfissa.



Autorizzato sotto: CC-BY-SA with attribution
Non affiliato con Stack Overflow
È legale questo KB? Sì, impara il perché
Autorizzato sotto: CC-BY-SA with attribution
Non affiliato con Stack Overflow
È legale questo KB? Sì, impara il perché