Qu’est-ce que la notation infixe ?
Une notation infixe est une notation dans laquelle une expression est écrite dans un format usuel ou normal. C'est une notation dans laquelle les opérateurs se situent entre les opérandes. Les exemples de notation infixe sont A+B, A*B, A/B, etc.
Comme nous pouvons le voir dans les exemples ci-dessus, tous les opérateurs existent entre les opérandes, ce sont donc des notations infixes. Par conséquent, la syntaxe de la notation infixe peut s’écrire comme suit :
Analyse des expressions Infix
Afin d'analyser une expression, nous devons prendre en compte deux choses, à savoir : Priorité des opérateurs et Associativité . La priorité des opérateurs désigne la priorité de tout opérateur sur un autre opérateur. Par exemple:
A + B * C → A + (B * C)
Comme l'opérateur de multiplication a une priorité plus élevée sur l'opérateur d'addition, l'expression B * C sera évaluée en premier. Le résultat de la multiplication de B * C est ajouté au A.
Ordre de priorité
| Les opérateurs | Symboles |
|---|---|
| Parenthèse | { }, ( ), [ ] |
| Notation exponentielle | ^ |
| Multiplication et division | *, / |
| Addition et soustraction | +, - |
L'associativité signifie lorsque les opérateurs avec la même priorité existent dans l'expression. Par exemple, dans l'expression, c'est-à-dire A + B - C, les opérateurs « + » et « - » ont la même priorité, ils sont donc évalués à l'aide de l'associativité. Puisque « + » et « - » sont associatifs à gauche, ils seraient évalués comme (A + B) - C.
Ordre d'associativité
| Les opérateurs | Associativité |
|---|---|
| ^ | De droite à gauche |
| *, / | De gauche à droite |
| +, - | De gauche à droite |
Comprenons l'associativité à travers un exemple.
caca
1 + 2*3 + 30/5
Puisque dans l’expression ci-dessus, * et / ont la même priorité, nous appliquerons donc la règle d’associativité. Comme nous pouvons observer dans le tableau ci-dessus que les opérateurs * et / ont l'associativité de gauche à droite, nous allons donc scanner à partir de l'opérateur le plus à gauche. L'opérateur qui arrive en premier sera évalué en premier. L'opérateur * apparaît avant l'opérateur / et la multiplication sera effectuée en premier.
1+ (2*3) + (30/5)
1+6+6 = 13
Qu'est-ce que la notation préfixe ?
Une notation préfixe est une autre forme d'expression mais elle ne nécessite pas d'autres informations telles que la préséance et l'associativité, alors qu'une notation infixe nécessite des informations sur la préséance et l'associativité. Il est également connu sous le nom notation polonaise . En notation préfixe, un opérateur précède les opérandes. La syntaxe de notation des préfixes est donnée ci-dessous :
Par exemple, si l'expression infixe est 5+1, alors l'expression préfixe correspondant à cette expression infixe est +51.
inclure la programmation c
Si l'expression infixe est :
a * b + c
↓
*ab+c
↓
+*abc (Expression de préfixe)
Prenons un autre exemple :
A+B*C
Première analyse : Dans l'expression ci-dessus, l'opérateur de multiplication a une priorité plus élevée que l'opérateur d'addition ; la notation du préfixe de B*C serait (*BC).
A + *BC
exemple de sous-chaîne en java
Deuxième analyse : Lors du deuxième scan, le préfixe serait :
+A *BC
Dans l'expression ci-dessus, nous utilisons deux analyses pour convertir l'infixe en expression de préfixe. Si l’expression est complexe, nous avons alors besoin d’un plus grand nombre d’analyses. Nous devons utiliser cette méthode qui ne nécessite qu’une seule analyse et fournit le résultat souhaité. Si nous obtenons le résultat souhaité en une seule analyse, alors l’algorithme serait efficace. Ceci n'est possible qu'en utilisant une pile.
Conversion d'Infix en préfixe à l'aide de Stack
K + L - M * N + (O ^ P) * W/U/V * T + Q
Si nous convertissons l’expression d’infixe en préfixe, nous devons d’abord inverser l’expression.
L'expression inverse serait :
Q + T * V/U/W * ) P^O(+ N*M - L + K
Pour obtenir l'expression de préfixe, nous avons créé un tableau composé de trois colonnes, à savoir l'expression d'entrée, la pile et l'expression de préfixe. Lorsque nous rencontrons un symbole, nous l’ajoutons simplement dans l’expression du préfixe. Si nous rencontrons l'opérateur, nous le pousserons dans la pile.
| Expression d'entrée | Empiler | Expression de préfixe |
|---|---|---|
| Q | Q | |
| + | + | Q |
| T | + | QT |
| * | +* | QT |
| DANS | +* | QTV |
| / | +*/ | QTV |
| DANS | +*/ | QTVU |
| / | +*// | QTVU |
| DANS | +*// | QTVUW |
| * | +*//* | QTVUW |
| ) | +*//*) | QTVUW |
| P. | +*//*) | QTVUWP |
| ^ | +*//*)^ | QTVUWP |
| Ô | +*//*)^ | 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'expression ci-dessus, c'est-à-dire QTVUWPO^*//*NM*LK+-++, n'est pas une expression finale. Nous devons inverser cette expression pour obtenir l’expression du préfixe.
Règles pour la conversion d'un infixe en expression de préfixe :
- Tout d’abord, inversez l’expression infixe donnée dans le problème.
- Parcourez l'expression de gauche à droite.
- Chaque fois que les opérandes arrivent, imprimez-les.
- Si l'opérateur arrive et que la pile s'avère vide, poussez simplement l'opérateur dans la pile.
- Si l'opérateur entrant a une priorité plus élevée que le TOP de la pile, poussez l'opérateur entrant dans la pile.
- Si l'opérateur entrant a la même priorité avec un TOP de la pile, poussez l'opérateur entrant dans la pile.
- Si l'opérateur entrant a une priorité inférieure au TOP de la pile, affichez et imprimez le haut de la pile. Testez à nouveau l'opérateur entrant par rapport au haut de la pile et extrayez l'opérateur de la pile jusqu'à ce qu'il trouve l'opérateur d'une priorité inférieure ou de même priorité.
- Si l'opérateur entrant a la même priorité avec le haut de la pile et que l'opérateur entrant est ^, alors faites apparaître le haut de la pile jusqu'à ce que la condition soit vraie. Si la condition n'est pas vraie, appuyez sur l'opérateur ^.
- Lorsque nous atteignons la fin de l'expression, affichez et imprimez tous les opérateurs du haut de la pile.
- Si l'opérateur est ')', poussez-le dans la pile.
- Si l'opérateur est '(', alors extrayez tous les opérateurs de la pile jusqu'à ce qu'il trouve ) crochet ouvrant dans la pile.
- Si le haut de la pile est ')', poussez l'opérateur sur la pile.
- À la fin, inversez la sortie.
Pseudocode de conversion d'infixe en préfixe
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))>