Struttura dei dati - Analisi delle espressioni

Il modo per scrivere espressioni aritmetiche è noto come a notation. Un'espressione aritmetica può essere scritta in tre notazioni differenti ma equivalenti, cioè senza cambiare l'essenza o l'output di un'espressione. Queste notazioni sono:

• Notazione infissa
• Notazione prefisso (polacco)
• Notazione Postfix (Reverse-Polish)

Queste notazioni prendono il nome dal modo in cui usano l'operatore nell'espressione. Impareremo lo stesso qui in questo capitolo.

Notazione infissa

Scriviamo espressione in infix notazione, ad esempio a - b + c, dove vengono utilizzati gli operatori in-tra operandi. È facile per noi umani leggere, scrivere e parlare in notazione infissa, ma lo stesso non va bene con i dispositivi informatici. Un algoritmo per elaborare la notazione infissa potrebbe essere difficile e costoso in termini di consumo di tempo e spazio.

Notazione prefisso

In questa notazione, l'operatore è prefixed agli operandi, cioè l'operatore viene scritto prima degli operandi. Per esempio,+ab. Questo è equivalente alla sua notazione infissaa + b. La notazione del prefisso è anche nota comePolish Notation.

Notazione postfissa

Questo stile di notazione è noto come Reversed Polish Notation. In questo stile di notazione, l'operatore èpostfixed agli operandi cioè, l'operatore viene scritto dopo gli operandi. Per esempio,ab+. Questo è equivalente alla sua notazione infissaa + b.

La tabella seguente cerca brevemente di mostrare la differenza in tutte e tre le notazioni:

Sr.No.	Notazione infissa	Notazione prefisso	Notazione postfissa
1	a + b	+ ab	ab +
2	(a + b) ∗ c	∗ + abc	ab + c ∗
3	a ∗ (b + c)	∗ a + bc	abc + ∗
4	a / b + c / d	+ / ab / cd	ab / cd / +
5	(a + b) ∗ (c + d)	∗ + ab + cd	ab + cd + ∗
6	((a + b) ∗ c) - d	- ∗ + abcd	ab + c ∗ d -

Espressioni di analisi

Come abbiamo discusso, non è un modo molto efficiente per progettare un algoritmo o un programma per analizzare le notazioni infisse. Invece, queste notazioni in infisso vengono prima convertite in notazioni con suffisso o prefisso e quindi calcolate.

Per analizzare qualsiasi espressione aritmetica, dobbiamo occuparci anche della precedenza e dell'associatività degli operatori.

Precedenza

Quando un operando si trova tra due diversi operatori, quale operatore prenderà l'operando per primo, viene deciso dalla precedenza di un operatore sugli altri. Ad esempio:

Poiché l'operazione di moltiplicazione ha la precedenza sull'addizione, b * c verrà valutato per primo. In seguito viene fornita una tabella di precedenza degli operatori.

Associatività

L'associatività descrive la regola in cui gli operatori con la stessa precedenza vengono visualizzati in un'espressione. Ad esempio, nell'espressione a + b - c, sia + che - hanno la stessa precedenza, quindi quale parte dell'espressione verrà valutata per prima è determinata dall'associatività di tali operatori. Qui, sia + che - sono associativi a sinistra, quindi l'espressione verrà valutata come(a + b) − c.

La precedenza e l'associatività determinano l'ordine di valutazione di un'espressione. Di seguito è riportata una tabella di precedenza e associatività degli operatori (dalla più alta alla più bassa):

Sr.No.	Operatore	Precedenza	Associatività
1	Esponenziazione ^	Più alta	Right Associative
2	Moltiplicazione (∗) e divisione (/)	Secondo più alto	Associativo di sinistra
3	Addizione (+) e sottrazione (-)	Il più basso	Associativo di sinistra

La tabella sopra mostra il comportamento predefinito degli operatori. In qualsiasi momento della valutazione dell'espressione, l'ordine può essere modificato utilizzando le parentesi. Ad esempio:

Nel a + b*c, la parte dell'espressione b*csarà valutato per primo, con la moltiplicazione come precedenza sull'addizione. Usiamo qui le parentesi pera + b da valutare prima, come (a + b)*c.

Algoritmo di valutazione Postfix

Vedremo ora l'algoritmo su come valutare la notazione suffisso -

Step 1 − scan the expression from left to right 
Step 2 − if it is an operand push it to stack 
Step 3 − if it is an operator pull operand from stack and perform operation 
Step 4 − store the output of step 3, back to stack 
Step 5 − scan the expression until all operands are consumed 
Step 6 − pop the stack and perform operation

Per vedere l'implementazione nel linguaggio di programmazione C, fare clic qui .