Analisi delle espressioni nella struttura dei dati: tipi di notazione, associatività e precedenza

L'analisi è il processo di analisi di una stringa di simboli, espressi in linguaggi naturali o informatici che accorderanno la grammatica formale . Analisi delle espressioni nella struttura dei dati significa la valutazione di espressioni aritmetiche e logiche. Per prima cosa, vediamo come si scrive un'espressione aritmetica:

• 9+9
• Cb

Un'espressione può essere scritta con costanti, variabili e simboli che possono fungere da operatore o parentesi. Tutta questa espressione deve seguire un insieme specifico di regole. Secondo questa regola, l'analisi dell'espressione viene eseguita in base alla grammatica.

Un'espressione aritmetica è espressa sotto forma di Notazione . Ora, ci sono tre modi per scrivere un'espressione in Aritmetica:

• Notazione infissa
• Notazione del prefisso (polacca).
• Notazione Postfix (Polacco inverso).

Tuttavia, quando l'espressione viene scritta, l'output dell'espressione desiderata rimane lo stesso. Prima di iniziare con i tipi di Notazione, vediamo cosa sono Associatività e Precedenza nell'espressione Parsing in Data Structure.

Se sei un principiante e sei interessato a saperne di più sulla scienza dei dati, dai un'occhiata ai nostri corsi di scienza dei dati delle migliori università.

Leggi: Grafici nella struttura dei dati

Associatività

Prima di iniziare, devi sapere cos'è la proprietà di Associatività; fornisce le regole per riordinare le parentesi in un'espressione per fornire una prova valida. Ciò significa che un riarrangiamento della parentesi deve dare lo stesso valore dell'equazione padre. Fornisce una regola valida per sostituire gli operatori.

In un'espressione contenente due o più operatori, l'operazione eseguita non ha importanza a meno che la sequenza di operandi non venga scambiata. Se l'espressione è scritta tra parentesi e infisso, la modifica della posizione non cambia il valore.

Poiché nelle lingue indoeuropee, le espressioni vengono lette da sinistra a destra, la maggior parte degli operatori infissi sono associativi a sinistra; gli operatori vengono valutati con la stessa precedenza. L'aumento del potere è la regola usata per considerare gli operatori infissi. Gli operatori di prefisso sono generalmente associativi a destra e gli operatori di suffisso sono associativi a sinistra.

In alcune lingue, agli operatori e agli operandi viene assegnato lo stesso valore, dove l'associatività non viene considerata esplicita questa sequenza linguistica. Mentre in alcuni linguaggi gli operatori non sono associativi, ciò rende necessario l'uso di espressioni complesse per l'uso delle parentesi, il che aumenta la complessità per i programmatori.

La precedenza nella struttura dei dati

Ordine di precedenza indica l'ordine che gli operatori devono seguire in una dichiarazione di espressioni. Questo è comunemente usato quando si lavora con Infix Notation.

Nella situazione di <operatore> <operando> <operatore> operando tra i due operatori, la preferenza di allocare l'operatore è piuttosto complicata. Pertanto, per il calcolo vengono seguite le regole di precedenza dell'operatore. Ad esempio, qui la moltiplicazione ha una precedenza maggiore e successivamente viene eseguita l'operazione di addizione.

• La regola più comune ma non così ovvia è che le operazioni di moltiplicazione e divisione devono essere eseguite prima dell'addizione e della sottrazione. Tipicamente, vengono raccolti nello stesso modo, quindi viene data uguale importanza a tutti gli operatori.
• Considerando questa operazione in un formato logico, la variazione è vista in "e" e "o". Molte lingue forniscono uguale importanza, dove all'operazione "o" viene data una precedenza maggiore. Alcune lingue considerano la moltiplicazione o "&", "&" addizione "o" la precedenza uguale, dove la maggior parte delle lingue fornisce operazioni aritmetiche con la precedenza più alta.
• Il sovraccarico è causato dall'assenza di una corretta assegnazione della precedenza. Molti linguaggi forniscono una precedenza di negazione (vero/falso) maggiore rispetto alle espressioni di algebra vettoriale, mentre alcuni forniscono una precedenza uguale.

Leggi anche: Idee per progetti sulla struttura dei dati

Tipi di notazione

Ora impariamo come la posizione dell'operatore decide il tipo di Notazione.

1. Notazione infissa

In Infix Notation, gli operatori vengono utilizzati tra gli operandi. Durante la lettura di un'espressione, Infix Notation è abbastanza facile per gli esseri umani. Ma è un bel dispendio di tempo e spazio per elaborare un argomento infisso quando si tratta di un algoritmo del computer. Es: p + q

<operandi> <operatori> <operandi>

Infix Notation necessita di ulteriori informazioni per eseguire la valutazione; le regole vengono costruite nel linguaggio delle espressioni usando l'operatore Associativity , Ad esempio: p * ( q + r ) / s

• Le regole di associatività suggeriscono che l'espressione deve essere eseguita da sinistra a destra, in modo tale che la moltiplicazione per p avvenga prima della divisione di q.
• Allo stesso modo, le regole per la precedenza suggeriscono che l'operazione di moltiplicazione e divisione viene eseguita prima dell'operazione di addizione e sottrazione.

2. Notazione del prefisso

Qui viene scritto prima l'operatore, seguito da un operando. È anche chiamato Notazione polacca. Es. +pq

<operatori> <operandi> <operandi>

Ad esempio: p * ( q + r ) / s

La valutazione deve essere eseguita da sinistra a destra e le parentesi non alterano o cambiano lo schema dell'equazione. Qui, l'addizione deve essere completata prima della moltiplicazione perché la posizione "+" è a sinistra di "*".

Qui, ogni operatore esegue operazioni sui valori che sono immediati alla loro sinistra. Ad esempio, il "+" sopra utilizza la "q" e la "r". Possiamo riassumere tra parentesi per rendere questo overt:

((p (qr +) *) s /)

Pertanto, "( )" considera e utilizza i due valori immediatamente precedenti a "p" e il risultato di +. Allo stesso modo, la "/" utilizza il risultato dell'espressione di moltiplicazione e la "s".

3. Notazione postfissa

Viene scritta la notazione Postfix, principalmente l'operando, seguita da un operatore. È anche chiamato notazione polacca inversa, ad esempio pq+

<operandi> <operandi> <operatori>

Come per Postfix, lo stesso dell'operazione Prefix dell'espressione è da sinistra a destra e "( )" non è necessario. Qui, gli operatori eseguono i due valori più vicini da destra. Nell'esempio seguente, le parentesi vengono aggiunte inutilmente, per chiarire che non vi è alcun impatto sulla valutazione.

(/ (* p (+ qr) ) s)

Qui i valori dell'operazione "la valutazione dell'operatore è da sinistra a destra" sono alla loro destra e se i valori stessi implicano calcoli, allora c'è un cambiamento nell'ordine di valutazione. Prendendo l'esempio sopra elencato, vedi "/" è l'operatore principale a sinistra.

Attende fino al completamento dell'operazione di moltiplicazione. E principalmente, l'operazione di moltiplicazione deve essere eseguita prima di iniziare il calcolo della divisione (e dall'esempio sopra, è chiaro che l'operazione di addizione deve essere completata prima dell'operazione di moltiplicazione).

Perché gli operatori di notazione Postfix usano il valore alla sua destra; tutti i valori che coinvolgono calcoli avranno il calcolo già completato mentre ci spostiamo a sinistra. Quindi, possiamo concludere che il calcolo dell'espressione non è uguale all'operazione dell'operatore Prefisso.

Per evidenziare tutte e tre le notazioni, gli operandi sono nello stesso ordine e gli operatori devono essere spostati per fornire il significato corretto durante il calcolo. Questo deve essere considerato in particolare quando si considerano gli operatori asimmetrici “-” e “/” per chiarire che pq è sempre qr a meno che non abbiano lo stesso valore; i valori sono equivalenti a “pq -” o “- pq”

P+q ≡ +pq ≡ pq+

Per esempio:

Infisso- p * q + r / s

Prefisso – pq * rs / +

Post correzione – + * pq / rs

Innanzitutto, per eseguire l'operazione, moltiplica p e q e poi dividi r per se, infine, aggiungi i risultati.

Sotto la tabella riassunti tra le tre Notazioni,

Notazione infissa	Notazione polacca	Notazione polacca inversa
p+q	+pq	pq+
(p+q)*r	+*pq	pqr+*
p*(q+r)	*p+qr	pqr*+ +
p÷q+r÷s	+÷pq÷rs	pq÷rs÷+
(pq)*(rs)	*-pq-rs	pq-rs-*

Conversione tra notazioni

*Per fornire una visione chiara, le parentesi vengono aggiunte nell'espressione,

Infisso	Postfisso	Prefisso
( (p * q) + (r / s) )	( (pq *) (rs /) +)	(+ (*) pq) (/ rs) )
((p * (q + r) ) / s)	( (p (qr +) *) s /)	(/ (* p (+ qr) ) s)
(p * (q + (r / s) ) )	(p (q (rs /) +) *)	(* p (+ q (/ rs) ) )

• È possibile avviare la conversione direttamente nei moduli tra parentesi mediante gli operatori tra parentesi, ad esempio (m + n) o (mn +) o (+ mn). Ora ripeti questo in tutti gli operatori rimuovendo le parentesi indesiderate.
• Ora usa questo trucco mostrato sopra per convertire e analizzare gli alberi: gli alberi di analisi equivalenti per ciascun nodo sono:

Checkout: struttura dati e algoritmo in Python

Conclusione

Analisi delle espressioni nelle notazioni struttura dati , infisse, suffisso e prefisso nelle espressioni aritmetiche sono piuttosto diverse ma hanno le stesse modalità di scrittura delle espressioni. La conoscenza di questi è essenziale nella scrittura di programmi.

In un linguaggio di programmazione per computer, l'espressione viene considerata e analizzata dalla stringa. La regola dell'associatività e della precedenza cambia abbastanza nelle diverse lingue.

Perché scegliere un corso di Data science con upGrad?

La scienza dei dati è uno dei campi in forte espansione dell'informatica. Le aziende hanno bisogno di programmatori che abbiano una buona conoscenza delle basi, che è fondamentale per la programmazione indipendentemente dal linguaggio di codifica.

upGrad si concentra sulla fornitura di lezioni approfondite e informative, che coprono ogni esigenza di base per diventare un data scientist. Programma Executive PG di 12 mesi di upGrad in Data Science. , offerto da IIIT Bangalore, è il primo corso certificato NASSCOM dell'India, che include un tutoraggio personalizzato 1:1 da parte di esperti del settore della scienza dei dati, che copre tutti i linguaggi di programmazione, gli strumenti e le librerie essenziali. Ti fornisce le migliori basi per iniziare il tuo lavoro di scienza dei dati ben retribuito.

Cosa sono le strutture dati?

Le strutture dati vengono utilizzate per organizzare i dati in memoria. Esistono diversi metodi per disporre i dati in memoria, inclusi array, elenchi, stack, code e molti altri. La struttura dei dati non è un linguaggio di programmazione come C, C++ o Java. Invece, è un insieme di tecniche che vengono utilizzate per organizzare i dati in memoria in qualsiasi linguaggio di programmazione. Una struttura dati è un metodo per organizzare, gestire e archiviare i dati in modo efficiente. Gli elementi di dati possono essere semplicemente attraversati con l'assistenza della struttura dei dati. È fondamentale per migliorare la velocità di un programma poiché il compito principale del programma è salvare e recuperare i dati dell'utente il più rapidamente possibile.

Quali sono gli usi reali dell'analisi dei dati?

Il processo di trasformazione dei dati da un formato all'altro è noto come analisi dei dati. Sono ampiamente utilizzati nei compilatori per l'analisi del codice del computer e la generazione del codice macchina. Il processo di conversione dei dati da un formato all'altro è noto come analisi dei dati. Poiché l'HTML non elaborato che riceviamo è difficile da capire, i parser vengono spesso impiegati nello scraping online. Richiediamo che i dati siano convertiti in un formato leggibile dall'uomo. Ciò potrebbe implicare la creazione di report utilizzando stringhe o tabelle HTML per fornire le informazioni più rilevanti.

In che modo Associatività e Precedenza aiutano nella strutturazione dei dati?

L'ordine di valutazione delle espressioni è determinato da due proprietà degli operatori: precedenza e associatività. La precedenza aiuta a stabilire come raggruppare i termini in un'espressione e come valutare un'espressione. Poiché la maggior parte delle espressioni utilizza il framework BODMAS, alcuni operatori hanno la precedenza su altri. Quando due operatori hanno la stessa precedenza in un'espressione, viene applicata la regola di associatività. A seconda delle preferenze del compilatore, l'associatività può essere da sinistra a destra o da destra a sinistra.