Avant de comprendre la conversion de la notation infixe en notation postfixe, nous devons connaître séparément les notations infixe et postfixe.

Un infixe et un suffixe sont les expressions. Une expression se compose de constantes, de variables et de symboles. Les symboles peuvent être des opérateurs ou des parenthèses. Tous ces composants doivent être organisés selon un ensemble de règles afin que toutes ces expressions puissent être évaluées à l'aide de l'ensemble de règles.

sous-chaîne chaîne java

Des exemples d'expressions sont :

5 + 6

UN B

(P*5)

Toutes les expressions ci-dessus ont une structure commune, c'est-à-dire que nous avons un opérateur entre les deux opérandes. Un opérande est un objet ou une valeur sur lequel l'opération doit être effectuée. Dans les expressions ci-dessus, 5, 6 sont les opérandes tandis que « + », « - » et « * » sont les opérateurs.

Qu’est-ce que la notation infixe ?

Lorsque l’opérateur est écrit entre les opérandes, on l’appelle alors notation infixe . L'opérande ne doit pas nécessairement être toujours une constante ou une variable ; cela peut aussi être une expression elle-même.

Par exemple,

(p + q) * (r + s)

Dans l'expression ci-dessus, les deux expressions de l'opérateur de multiplication sont les opérandes, c'est-à-dire (p + q) , et (r + s) sont les opérandes.

Dans l’expression ci-dessus, il y a trois opérateurs. Les opérandes du premier opérateur plus sont p et q, les opérandes du deuxième opérateur plus sont r et s. Lors de l'exécution du opérations sur l’expression, nous devons suivre un ensemble de règles pour évaluer le résultat. Dans le au-dessus de l’expression, une opération d’addition serait effectuée sur les deux expressions, c’est-à-dire p+q et r+s, puis l’opération de multiplication serait effectuée.

La syntaxe de la notation infixe est donnée ci-dessous :

S’il n’y a qu’un seul opérateur dans l’expression, nous n’avons besoin d’appliquer aucune règle. Par exemple, 5 + 2 ; dans cette expression, une opération d'addition peut être effectuée entre les deux opérandes (5 et 2), et le résultat de l'opération serait 7.

S'il existe plusieurs opérateurs dans l'expression, une règle doit être suivie pour évaluer l'expression.

Si l'expression est :

4+6*2

Si l'opérateur plus est évalué en premier, alors l'expression ressemblerait à :

10 * 2 = 20

Si l’opérateur de multiplication est évalué en premier, alors l’expression ressemblerait à :

4 + 12 = 16

Le problème ci-dessus peut être résolu en suivant les règles de priorité des opérateurs. Dans l'expression algébrique, l'ordre de priorité des opérateurs est donné dans le tableau ci-dessous :

La première préférence est donnée à la parenthèse ; alors la préférence suivante est donnée aux exposants. Dans le cas d’opérateurs à exposants multiples, alors l’opération sera appliquée de droite à gauche.

chaîne.valeurde

Par exemple:

2 ^ 2 ^ 3 = 2 ^ 8

= 256

Après l’évaluation des opérateurs d’exposant, de multiplication et de division. Si les deux opérateurs sont présents dans l’expression, alors l’opération sera appliquée de gauche à droite.

La préférence suivante est donnée à l'addition et à la soustraction. Si les deux opérateurs sont disponibles dans l’expression, alors on passe de gauche à droite.

Les opérateurs qui ont la même priorité appelés associativité des opérateurs . Si nous allons de gauche à droite, on parle alors d’associatif à gauche. Si nous allons de droite à gauche, on parle alors d’associatif à droite.

Problème avec la notation infixe

Pour évaluer l'expression infixe, nous devons connaître le priorité des opérateurs règles, et si les opérateurs ont la même priorité, alors nous devrions suivre les associativité règles. L'utilisation des parenthèses est très importante en notation infixe pour contrôler l'ordre dans lequel l'opération doit être effectuée. Les parenthèses améliorent la lisibilité de l'expression. Une expression infixe est la manière la plus courante d’écrire une expression, mais il n’est pas facile d’analyser et d’évaluer l’expression infixe sans ambiguïté. Ainsi, les mathématiciens et les logiciens ont étudié ce problème et ont découvert deux autres manières d'écrire des expressions qui sont le préfixe et le suffixe. Les deux expressions ne nécessitent aucune parenthèse et peuvent être analysées sans ambiguïté. Il ne nécessite pas de règles de priorité des opérateurs ni d’associativité.

Expression postfixe

L'expression postfixe est une expression dans laquelle l'opérateur est écrit après les opérandes. Par exemple, l'expression postfixée de notation infixe ( 2+3) peut s'écrire 23+.

Voici quelques points clés concernant l'expression postfixe :

• Dans l'expression postfixe, les opérations sont effectuées dans l'ordre dans lequel elles ont été écrites, de gauche à droite.
• Cela ne nécessite aucune parenthèse.
• Nous n'avons pas besoin d'appliquer des règles de préséance des opérateurs et des règles d'associativité.

Algorithme pour évaluer l'expression postfixe

• Parcourez l'expression de gauche à droite jusqu'à ce que nous rencontrions un opérateur.
• Effectuer l'opération
• Remplacez l'expression par sa valeur calculée.
• Répétez les étapes 1 à 3 jusqu'à ce qu'il n'y ait plus d'opérateurs.

Comprenons l'algorithme ci-dessus à travers un exemple.

Expression infixe : 2 + 3 * 4

Nous allons commencer à numériser à partir de la gauche de l’expression. L'opérateur de multiplication est un opérateur qui apparaît en premier lors du balayage de gauche à droite. Maintenant, l'expression serait :

Java pgm

Expression = 2 + 34*

= 2 + 12

Encore une fois, nous balayerons de gauche à droite, et l'expression serait :

Expression = 2 12 +

= 14

Évaluation de l'expression postfix à l'aide de la pile.

• Parcourez l'expression de gauche à droite.
• Si nous rencontrons un opérande dans l’expression, alors nous poussons l’opérande dans la pile.
• Lorsque nous rencontrons un opérateur dans l'expression, nous supprimons les opérandes correspondants de la pile.
• Lorsque nous avons terminé le scan de l'expression, la valeur finale reste dans la pile.

Comprenons l'évaluation de l'expression postfix à l'aide de la pile.

contient la sous-chaîne java

Exemple 1 : Expression suffixe : 2 3 4 * +

Le résultat de l’expression ci-dessus est 14.

Exemple 2 : Expression suffixe : 3 4 * 2 5 * +

Le résultat de l’expression ci-dessus est 22.

Algorithme pour évaluer l'expression postfixe

1. Lire un personnage
2. Si le caractère est un chiffre, convertissez-le en entier et placez l'entier dans la pile.
3. Si le personnage est un opérateur,
   • Extrayez les éléments de la pile deux fois pour obtenir deux opérandes.
   • Effectuer l'opération
   • Poussez le résultat dans la pile.

Conversion d'infixe en suffixe

Ici, nous utiliserons la structure de données de la pile pour la conversion de l'expression infixe en expression préfixe. Chaque fois qu'un opérateur se rencontre, nous le poussons dans la pile. Si nous rencontrons un opérande, nous l’ajoutons à l’expression.

Règles pour la conversion d'une expression infixe en expression postfixe

1. Imprimez l'opérande dès son arrivée.
2. Si la pile est vide ou contient une parenthèse gauche en haut, poussez l'opérateur entrant sur la pile.
3. Si le symbole entrant est '(', placez-le sur la pile.
4. Si le symbole entrant est ')', ouvrez la pile et imprimez les opérateurs jusqu'à ce que la parenthèse gauche soit trouvée.
5. Si le symbole entrant a une priorité plus élevée que le haut de la pile, placez-le sur la pile.
6. Si le symbole entrant a une priorité inférieure à celle du haut de la pile, affichez et imprimez le haut de la pile. Testez ensuite l’opérateur entrant par rapport au nouveau sommet de la pile.
7. Si l'opérateur entrant a la même priorité avec le haut de la pile, utilisez les règles d'associativité. Si l'associativité est de gauche à droite, affichez et imprimez le haut de la pile, puis poussez l'opérateur entrant. Si l'associativité est de droite à gauche, poussez l'opérateur entrant.
8. A la fin de l'expression, affichez et imprimez tous les opérateurs de la pile.

Comprenons à travers un exemple.

Expression infixe : K + L - M*N + (O^P) * W/U/V * T + Q

L'expression postfixée finale de l'expression infixe (K + L - M*N + (O^P) * W/U/V * T + Q) est KL+MN*-OP^W*U/V/T*+Q+ .