Cos'è la notazione infissa?
Una notazione infissa è una notazione in cui un'espressione è scritta in un formato consueto o normale. È una notazione in cui gli operatori si trovano tra gli operandi. Gli esempi di notazione infissa sono A+B, A*B, A/B, ecc.
Come possiamo vedere negli esempi precedenti, tutti gli operatori esistono tra gli operandi, quindi sono notazioni infisse. Pertanto, la sintassi della notazione infissa può essere scritta come:
Analisi delle espressioni infisse
Per analizzare qualsiasi espressione, dobbiamo occuparci di due cose, vale a dire Precedenza degli operatori E Associatività . Per precedenza degli operatori si intende la precedenza di qualsiasi operatore rispetto a un altro operatore. Per esempio:
A + B * C → A + (B * C)
Poiché l'operatore di moltiplicazione ha una precedenza maggiore rispetto all'operatore di addizione, l'espressione B * C verrà valutata per prima. Il risultato della moltiplicazione di B*C viene sommato ad A.
Ordine di precedenza
| Operatori | Simboli |
|---|---|
| Parentesi | { }, ( ), [ ] |
| Notazione esponenziale | ^ |
| Moltiplicazione e divisione | *, / |
| Addizione e sottrazione | +, - |
Associatività significa quando nell'espressione esistono operatori con la stessa precedenza. Ad esempio, nell'espressione A + B - C, gli operatori '+' e '-' hanno la stessa precedenza, quindi vengono valutati con l'aiuto dell'associatività. Poiché sia '+' che '-' sono associativi a sinistra, verrebbero valutati come (A + B) - C.
Ordine di associatività
| Operatori | Associatività |
|---|---|
| ^ | Da destra a sinistra |
| *, / | Da sinistra a destra |
| +, - | Da sinistra a destra |
Capiamo l'associatività attraverso un esempio.
conversione da stringa Java a int
1 + 2*3 + 30/5
Poiché nell'espressione precedente * e / hanno la stessa precedenza, applicheremo la regola di associatività. Come possiamo osservare nella tabella sopra che gli operatori * e / hanno l'associatività da sinistra a destra, quindi eseguiremo la scansione dall'operatore più a sinistra. L'operatore che arriva per primo verrà valutato per primo. L'operatore * appare prima dell'operatore / e la moltiplicazione verrà eseguita per prima.
1+ (2*3) + (30/5)
1+6+6 = 13
ipconfig gratuito di Linux
Cos'è la notazione del prefisso?
Una notazione con prefisso è un'altra forma di espressione ma non richiede altre informazioni come precedenza e associatività, mentre una notazione infissa richiede informazioni di precedenza e associatività. È anche noto come notazione polacca . Nella notazione del prefisso, un operatore viene prima degli operandi. La sintassi della notazione del prefisso è riportata di seguito:
Per esempio, se l'espressione infissa è 5+1, allora l'espressione con prefisso corrispondente a questa espressione infissa è +51.
Se l'espressione infissa è:
a*b+c
↓
*ab+c
c booleano
↓
+*abc (espressione prefisso)
Consideriamo un altro esempio:
A + B * C
Prima scansione: Nell'espressione precedente, l'operatore di moltiplicazione ha una precedenza maggiore rispetto all'operatore di addizione; la notazione del prefisso di B*C sarebbe (*BC).
A+*BC
Seconda scansione: Nella seconda scansione, il prefisso sarebbe:
+A *BC
Nell'espressione precedente, utilizziamo due scansioni per convertire l'espressione da infisso a prefisso. Se l'espressione è complessa, avremo bisogno di un numero maggiore di scansioni. Dobbiamo utilizzare quel metodo che richiede una sola scansione e fornisce il risultato desiderato. Se ottenessimo l'output desiderato attraverso una scansione, l'algoritmo sarebbe efficiente. Ciò è possibile solo utilizzando uno stack.
Conversione di Infisso in Prefisso utilizzando Stack
K + L - M * N + (O^P) * W/U/V * T + Q
Se stiamo convertendo l'espressione da infisso a prefisso, dobbiamo prima invertire l'espressione.
L'espressione inversa sarebbe:
Q + T * V/U/W * ) P^O(+ N*M - L + K
Per ottenere l'espressione del prefisso, abbiamo creato una tabella composta da tre colonne, ovvero espressione di input, stack ed espressione del prefisso. Quando incontriamo un simbolo, lo aggiungiamo semplicemente all'espressione del prefisso. Se incontriamo l'operatore, lo inseriremo nello stack.
stringa di formato java
| Espressione di input | Pila | Espressione del prefisso |
|---|---|---|
| Q | Q | |
| + | + | Q |
| T | + | QT |
| * | +* | QT |
| IN | +* | QTV |
| / | +*/ | QTV |
| IN | +*/ | QTVU |
| / | +*// | QTVU |
| IN | +*// | QTVUW |
| * | +*//* | QTVUW |
| ) | +*//*) | QTVUW |
| P | +*//*) | QTVUWP |
| ^ | +*//*)^ | QTVUWP |
| O | +*//*)^ | QTVUWPO |
| ( | +*//* | QTVUWPO^ |
| + | ++ | QTVUWPO^*//* |
| N | ++ | QTVUWPO^*//*N |
| * | ++* | QTVUWPO^*//*N |
| M | ++* | QTVUWPO^*//*NM |
| - | ++- | QTVUWPO^*//*NM* |
| l | ++- | QTVUWPO^*//*NM*L |
| + | +-+ | QTVUWPO^*//*NM*L |
| K | +-+ | QTVUWPO^*//*NM*LK |
| QTVUWPO^*//*NM*LK+-++ |
L'espressione precedente, ovvero QTVUWPO^*//*NM*LK+-++, non è un'espressione finale. Dobbiamo invertire questa espressione per ottenere l'espressione del prefisso.
Regole per la conversione dell'espressione infisso in prefisso:
- Innanzitutto, invertire l'espressione infissa fornita nel problema.
- Scansiona l'espressione da sinistra a destra.
- Ogni volta che arrivano gli operandi, li stampa.
- Se l'operatore arriva e la pila risulta essere vuota, è sufficiente spingere l'operatore nella pila.
- Se l'operatore in entrata ha una precedenza maggiore rispetto al TOP dello stack, inserisci l'operatore in entrata nello stack.
- Se l'operatore in entrata ha la stessa precedenza con un TOP dello stack, inserisci l'operatore in entrata nello stack.
- Se l'operatore in entrata ha una precedenza inferiore rispetto al TOP dello stack, estrai e stampa la parte superiore dello stack. Testare nuovamente l'operatore in entrata confrontandolo con la parte superiore dello stack ed estrarre l'operatore dallo stack finché non trova l'operatore con una precedenza inferiore o con la stessa precedenza.
- Se l'operatore in entrata ha la stessa precedenza con la parte superiore dello stack e l'operatore in entrata è ^, inserisci la parte superiore dello stack finché la condizione non è vera. Se la condizione non è vera, premi l'operatore ^.
- Quando raggiungiamo la fine dell'espressione, estraiamo e stampiamo tutti gli operatori dalla cima dello stack.
- Se l'operatore è ')', inserirlo nello stack.
- Se l'operatore è '(', inserisci tutti gli operatori dallo stack finché non trova una parentesi di apertura nello stack.
- Se la parte superiore dello stack è ')', spinge l'operatore sullo stack.
- Alla fine, invertire l'output.
Pseudocodice della conversione da infisso a prefisso
Function InfixtoPrefix( stack, infix) infix = reverse(infix) loop i = 0 to infix.length if infix[i] is operand → prefix+= infix[i] else if infix[i] is '(' → stack.push(infix[i]) else if infix[i] is ')' → pop and print the values of stack till the symbol ')' is not found else if infix[i] is an operator(+, -, *, /, ^) → if the stack is empty then push infix[i] on the top of the stack. Else → If precedence(infix[i] > precedence(stack.top)) → Push infix[i] on the top of the stack else if(infix[i] == precedence(stack.top) && infix[i] == '^') → Pop and print the top values of the stack till the condition is true → Push infix[i] into the stack else if(infix[i] == precedence(stack.top)) → Push infix[i] on to the stack Else if(infix[i] <precedence(stack.top)) → pop the stack values and print them till is not empty infix[i] < precedence(stack.top) push on to end loop remaining elements of prefix="reverse(prefix)" return pre> <hr></precedence(stack.top))>