Structure des données - Analyse des expressions
La façon d'écrire une expression arithmétique est connue sous le nom de notation. Une expression arithmétique peut être écrite dans trois notations différentes mais équivalentes, c'est-à-dire sans changer l'essence ou la sortie d'une expression. Ces notations sont -
- Notation infixe
- Notation de préfixe (polonais)
- Notation Postfix (polonaise inversée)
Ces notations sont nommées selon la manière dont elles utilisent l'opérateur dans l'expression. Nous apprendrons la même chose ici dans ce chapitre.
Notation infixe
Nous écrivons l'expression dans infix notation, par exemple a - b + c, où les opérateurs sont utilisés in-entre les opérandes. Il est facile pour nous, humains, de lire, d'écrire et de parler en notation infixe, mais la même chose ne va pas bien avec les appareils informatiques. Un algorithme pour traiter la notation infixe pourrait être difficile et coûteux en termes de consommation de temps et d'espace.
Notation de préfixe
Dans cette notation, l'opérateur est prefixed aux opérandes, c'est-à-dire que l'opérateur est écrit avant les opérandes. Par exemple,+ab. Ceci est équivalent à sa notation infixea + b. La notation de préfixe est également connue sous le nom dePolish Notation.
Notation Postfix
Ce style de notation est connu sous le nom de Reversed Polish Notation. Dans ce style de notation, l'opérateur estpostfixed aux opérandes, c'est-à-dire que l'opérateur est écrit après les opérandes. Par exemple,ab+. Ceci est équivalent à sa notation infixea + b.
Le tableau suivant essaie brièvement de montrer la différence entre les trois notations -
N ° Sr. | Notation infixe | Notation de préfixe | Notation Postfix |
---|---|---|---|
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 - |
Analyse des expressions
Comme nous l'avons vu, ce n'est pas un moyen très efficace de concevoir un algorithme ou un programme pour analyser les notations d'infixe. Au lieu de cela, ces notations d'infixe sont d'abord converties en notations de suffixe ou de préfixe, puis calculées.
Pour analyser une expression arithmétique, nous devons également prendre en compte la priorité des opérateurs et l'associativité.
Priorité
Lorsqu'un opérande est entre deux opérateurs différents, quel opérateur prendra l'opérande en premier, est décidé par la priorité d'un opérateur sur les autres. Par exemple -
![](https://assets.edu.lat/data_structures_algorithms/images/operator_precedence.jpg)
Comme l'opération de multiplication a priorité sur l'addition, b * c sera évalué en premier. Un tableau de priorité des opérateurs est fourni ultérieurement.
Associativité
L'associativité décrit la règle dans laquelle les opérateurs de même priorité apparaissent dans une expression. Par exemple, dans l'expression a + b - c, + et - ont la même priorité, alors quelle partie de l'expression sera évaluée en premier est déterminée par l'associativité de ces opérateurs. Ici, + et - sont laissés associatifs, donc l'expression sera évaluée comme(a + b) − c.
La préséance et l'associativité déterminent l'ordre d'évaluation d'une expression. Voici une table de priorité des opérateurs et d'associativité (du plus élevé au plus bas) -
N ° Sr. | Opérateur | Priorité | Associativité |
---|---|---|---|
1 | Exponentiation ^ | Le plus élevé | Associatif droit |
2 | Multiplication (∗) & Division (/) | Deuxième plus haut | Associatif gauche |
3 | Addition (+) et soustraction (-) | Le plus bas | Associatif gauche |
Le tableau ci-dessus montre le comportement par défaut des opérateurs. À tout moment de l'évaluation de l'expression, l'ordre peut être modifié à l'aide de parenthèses. Par exemple -
Dans a + b*c, la partie expression b*csera évalué en premier, avec la multiplication comme priorité sur l'addition. Nous utilisons ici des parenthèses poura + b à évaluer en premier, comme (a + b)*c.
Algorithme d'évaluation de Postfix
Nous allons maintenant examiner l'algorithme sur la façon d'évaluer la notation postfixe -
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
Pour voir l'implémentation en langage de programmation C, veuillez cliquer ici .