Prima di comprendere la conversione dalla notazione infissa a quella postfissa, dovremmo conoscere separatamente le notazioni infissa e postfissa.

Un infisso e un postfisso sono le espressioni. Un'espressione è composta da costanti, variabili e simboli. I simboli possono essere operatori o parentesi. Tutti questi componenti devono essere organizzati secondo un insieme di regole in modo che tutte queste espressioni possano essere valutate utilizzando l'insieme di regole.

Esempi di espressioni sono:

5 + 6

A-B

(P*5)

Tutte le espressioni precedenti hanno una struttura comune, ovvero abbiamo un operatore tra i due operandi. Un operando è un oggetto o un valore su cui deve essere eseguita l'operazione. Nelle espressioni precedenti, 5, 6 sono gli operandi mentre '+', '-' e '*' sono gli operatori.

Cos'è la notazione infissa?

Quando l'operatore è scritto tra gli operandi, è noto come notazione infissa . L'operando non deve essere sempre una costante o una variabile; può anche essere un'espressione stessa.

Per esempio,

(p + q) * (r + s)

sei giunto

Nell'espressione precedente, entrambe le espressioni dell'operatore di moltiplicazione sono gli operandi, ovvero (p + q) , E (r + s) sono gli operandi.

Nell'espressione precedente ci sono tre operatori. Gli operandi per il primo operatore più sono p e q, gli operandi per il secondo operatore più sono r e s. Durante l'esecuzione del operazioni sull'espressione, dobbiamo seguire alcune regole per valutare il risultato. Nel sopra l'espressione, l'operazione di addizione verrebbe eseguita sulle due espressioni, ovvero p+q e r+s, e quindi l'operazione di moltiplicazione verrebbe eseguita.

La sintassi della notazione infissa è riportata di seguito:

Se nell'espressione è presente un solo operatore, non è necessario applicare alcuna regola. Ad esempio, 5 + 2; in questa espressione è possibile eseguire un'operazione di addizione tra i due operandi (5 e 2) e il risultato dell'operazione sarebbe 7.

Se nell'espressione sono presenti più operatori, è necessario seguire alcune regole per valutare l'espressione.

Se l'espressione è:

come trovare numeri bloccati su Android

4+6*2

Se l'operatore più viene valutato per primo, l'espressione sarebbe simile a:

10*2 = 20

Se viene valutato prima l'operatore di moltiplicazione, l'espressione sarebbe simile a:

4 + 12 = 16

exclp

Il problema di cui sopra può essere risolto seguendo le regole di precedenza degli operatori. Nell'espressione algebrica, l'ordine di precedenza degli operatori è riportato nella tabella seguente:

La prima preferenza è data alla parentesi; poi viene data la preferenza agli esponenti. Nel caso di operatori con esponente multiplo, l'operazione verrà applicata da destra a sinistra.

Per esempio:

2^2^3 = 2^8

= 256

Dopo l'esponente, vengono valutati gli operatori di moltiplicazione e divisione. Se nell'espressione sono presenti entrambi gli operatori, l'operazione verrà applicata da sinistra a destra.

La preferenza successiva è data all'addizione e alla sottrazione. Se nell'espressione sono disponibili entrambi gli operatori, si procede da sinistra a destra.

Gli operatori che hanno la stessa precedenza vengono definiti come associatività degli operatori . Se andiamo da sinistra a destra, allora è noto come associativo di sinistra. Se andiamo da destra a sinistra, allora è noto come associativo di destra.

Problema con la notazione infissa

Per valutare l'espressione infissa, dovremmo conoscere the precedenza dell'operatore regole, e se gli operatori hanno la stessa precedenza, allora dovremmo seguire le regole associatività regole. L'uso delle parentesi è molto importante nella notazione infissa per controllare l'ordine in cui l'operazione deve essere eseguita. Le parentesi migliorano la leggibilità dell'espressione. Un'espressione infissa è il modo più comune di scrivere un'espressione, ma non è facile analizzare e valutare l'espressione infissa senza ambiguità. Quindi, matematici e logici hanno studiato questo problema e hanno scoperto altri due modi di scrivere le espressioni che sono prefisso e postfisso. Entrambe le espressioni non richiedono parentesi e possono essere analizzate senza ambiguità. Non richiede regole di precedenza degli operatori e di associatività.

Espressione suffissa

L'espressione suffissa è un'espressione in cui l'operatore è scritto dopo gli operandi. Ad esempio, l'espressione suffissa della notazione infissa (2+3) può essere scritta come 23+.

Alcuni punti chiave riguardanti l'espressione suffissa sono:

• Nelle espressioni suffisse, le operazioni vengono eseguite nell'ordine in cui sono scritte da sinistra a destra.
• Non richiede alcuna parentesi.
• Non abbiamo bisogno di applicare regole di precedenza degli operatori e regole di associatività.

Algoritmo per valutare l'espressione suffissa

• Scansiona l'espressione da sinistra a destra finché non incontriamo un operatore.
• Eseguire l'operazione
• Sostituisci l'espressione con il suo valore calcolato.
• Ripetere i passaggi da 1 a 3 finché non esistono più operatori.

Comprendiamo l'algoritmo di cui sopra attraverso un esempio.

Espressione infissa: 2 + 3 * 4

Inizieremo la scansione dalla maggior parte a sinistra dell'espressione. L'operatore di moltiplicazione è un operatore che appare per primo durante la scansione da sinistra a destra. Ora l'espressione sarebbe:

confronto con Java

Espressione = 2 + 34*

= 2 + 12

Ancora una volta, eseguiremo la scansione da sinistra a destra e l'espressione sarebbe:

Espressione = 2 12 +

= 14

Valutazione dell'espressione suffissa utilizzando lo stack.

• Scansiona l'espressione da sinistra a destra.
• Se incontriamo qualche operando nell'espressione, inseriamo l'operando nello stack.
• Quando incontriamo un operatore nell'espressione, estraiamo gli operandi corrispondenti dallo stack.
• Una volta terminata la scansione dell'espressione, il valore finale rimane nello stack.

Comprendiamo la valutazione dell'espressione suffissa utilizzando lo stack.

Esempio 1: Espressione suffissa: 2 3 4 * +

Il risultato dell'espressione precedente è 14.

Esempio 2: Espressione suffissa: 3 4 * 2 5 * +

Il risultato dell'espressione precedente è 22.

programma c per il confronto di stringhe

Algoritmo per valutare l'espressione suffissa

1. Leggi un personaggio
2. Se il carattere è una cifra, converti il ​​carattere in int e inserisci il numero intero nello stack.
3. Se il personaggio è un operatore,
   • Estrai gli elementi dallo stack due volte ottenendo due operandi.
   • Eseguire l'operazione
   • Metti il ​​risultato nello stack.

Conversione dell'infisso in suffisso

Qui utilizzeremo la struttura dei dati dello stack per la conversione dell'espressione infissa in un'espressione con prefisso. Ogni volta che incontreremo un operatore, lo inseriremo nello stack. Se incontriamo un operando, aggiungiamo l'operando all'espressione.

Regole per la conversione da espressione infissa a suffissa

1. Stampa l'operando man mano che arrivano.
2. Se lo stack è vuoto o contiene una parentesi aperta in alto, inserisci l'operatore in entrata nello stack.
3. Se il simbolo in arrivo è '(', mettilo nello stack.
4. Se il simbolo in arrivo è ')', estrai lo stack e stampa gli operatori finché non viene trovata la parentesi sinistra.
5. Se il simbolo in arrivo ha una precedenza maggiore rispetto alla cima della pila, mettilo in pila.
6. Se il simbolo in arrivo ha una precedenza inferiore rispetto alla cima dello stack, estrai e stampa la cima dello stack. Quindi testa l'operatore in entrata rispetto alla nuova cima dello stack.
7. Se l'operatore in entrata ha la stessa precedenza con la parte superiore dello stack, utilizzare le regole di associatività. Se l'associatività va da sinistra a destra, apri e stampa la parte superiore dello stack, quindi spingi l'operatore in entrata. Se l'associatività va da destra a sinistra, premi l'operatore in entrata.
8. Alla fine dell'espressione, estrai e stampa tutti gli operatori dello stack.

Capiamo attraverso un esempio.

Espressione infissa: K + L - M*N + (O^P) * W/U/V * T + Q

L'espressione suffissa finale dell'espressione infissa (K + L - M*N + (O^P) * W/U/V * T + Q) è KL+MN*-OP^W*U/V/T*+Q+ .