Écrivez un programme pour convertir une expression Infix en forme Postfix.

Expression infixe : L'expression de la forme a opérateur b (a + b), c'est-à-dire lorsqu'un opérateur est entre chaque paire d'opérandes.
Expression suffixe : L'expression de la forme opérateur a b (ab+), c'est-à-dire lorsque chaque paire d'opérandes est suivie par un opérateur.

Exemples:

Saisir: A + B * C + D
Sortir: ABC*+D+

Saisir: ((A + B) – C * (D/E)) + F
Sortir: AB+CDE/*-F+

Pourquoi une représentation postfixée de l'expression ?

Le compilateur analyse l'expression de gauche à droite ou de droite à gauche.
Considérons l'expression : a + b * c + d

• Le compilateur analyse d'abord l'expression pour évaluer l'expression b * c, puis analyse à nouveau l'expression pour y ajouter a.
• Le résultat est ensuite ajouté à d après une autre analyse.

Les analyses répétées le rendent très inefficace. Les expressions infixes sont facilement lisibles et résolubles par les humains, alors que l'ordinateur ne peut pas différencier facilement les opérateurs et les parenthèses. Il est donc préférable de convertir l'expression sous forme de suffixe (ou de préfixe) avant l'évaluation.

L'expression correspondante sous forme de suffixe est abc*+d+ . Les expressions postfix peuvent être facilement évaluées à l'aide d'une pile.

Comment convertir une expression Infix en expression Postfix ?

Pour convertir une expression infixe en expression postfixe, utilisez le Vous trouverez ci-dessous les étapes pour mettre en œuvre l’idée ci-dessus :

1. Scannez l'expression infixe de gauche à droite .

2. Vous trouverez ci-dessous les étapes pour mettre en œuvre l’idée ci-dessus :
   1. Si le caractère numérisé est un opérande, placez-le dans l'expression suffixe.
   3. Vous trouverez ci-dessous les étapes pour mettre en œuvre l’idée ci-dessus :
      1. Sinon, procédez comme suit
         • Si la priorité et l'associativité de l'opérateur analysé sont supérieures à la priorité et à l'associativité de l'opérateur dans la pile [ou si la pile est vide ou si la pile contient un ' ( ‘ ], puis poussez-le dans la pile. [' ^ ‘ l’opérateur a raison associatif et d’autres opérateurs comme ‘ + ',' – ',' * ' et ' / 'sont associatifs à gauche].
           • Vérifiez particulièrement une condition dans laquelle l'opérateur en haut de la pile et l'opérateur scanné sont tous deux « ^ ‘. Dans cette condition, la préséance de l’opérateur scanné est plus élevée en raison de sa bonne associativité. Il sera donc poussé dans la pile des opérateurs.
           • Dans tous les autres cas, lorsque le haut de la pile d'opérateurs est le même que l'opérateur numérisé, supprimez l'opérateur de la pile en raison de l'associativité gauche en raison de laquelle l'opérateur numérisé a moins de priorité.
         • Sinon, extrayez de la pile tous les opérateurs dont la priorité est supérieure ou égale à celle de l'opérateur analysé.
           • Après cela, poussez l'opérateur numérisé vers la pile. (Si vous rencontrez des parenthèses lors de l'extraction, arrêtez-vous là et poussez l'opérateur numérisé dans la pile.)
      4. Vous trouverez ci-dessous les étapes pour mettre en œuvre l’idée ci-dessus :
         1. Si le caractère numérisé est un « ( ‘, poussez-le vers la pile.
         5. Vous trouverez ci-dessous les étapes pour mettre en œuvre l’idée ci-dessus :
            1. Si le caractère numérisé est un « ) ', ouvrez la pile et affichez-la jusqu'à ce qu'un ' ( ' est rencontré et supprimez les deux parenthèses.
            6. Vous trouverez ci-dessous les étapes pour mettre en œuvre l’idée ci-dessus :
               1. Répétez les étapes 2-5 jusqu'à ce que l'expression infixe soit analysée.
               7. Vous trouverez ci-dessous les étapes pour mettre en œuvre l’idée ci-dessus :

                  cm en pieds et pouces

                  1. Une fois l'analyse terminée, ouvrez la pile et ajoutez les opérateurs dans l'expression suffixe jusqu'à ce qu'elle ne soit pas vide.
                  8. Vous trouverez ci-dessous les étapes pour mettre en œuvre l’idée ci-dessus :
                     1. Enfin, imprimez l’expression postfixe.

                     Vous trouverez ci-dessous les étapes pour mettre en œuvre l’idée ci-dessus :

                     1. Illustration:

                     Vous trouverez ci-dessous les étapes pour mettre en œuvre l’idée ci-dessus :

                     1. Suivez l'illustration ci-dessous pour une meilleure compréhension
                        Vous trouverez ci-dessous les étapes pour mettre en œuvre l’idée ci-dessus :

                        1. Considérez l'expression infixe exp = a+b*c+d
                           et l'expression infixe est analysée à l'aide de l'itérateur je , qui est initialisé comme je = 0 .

                           1ère étape : Ici i = 0 et exp[i] = 'a', c'est-à-dire un opérande. Ajoutez donc ceci dans l'expression postfixe. Donc, suffixe = a .

                           

                           Ajoutez « a » dans le suffixe

                           2ème étape : Ici i = 1 et exp[i] = '+' c'est-à-dire un opérateur. Poussez-le dans la pile. suffixe = a et pile = {+} .

                           

                           Appuyez sur « + » dans la pile

                           3ème étape : Maintenant, je = 2 et exp[i] = 'b', c'est-à-dire un opérande. Ajoutez donc ceci dans l'expression postfixe. suffixe = ab et pile = {+} .

                           

                           Ajoutez « b » dans le suffixe

                           4ème étape : Maintenant, je = 3 et exp[i] = '*', c'est-à-dire un opérateur. Poussez-le dans la pile. suffixe = ab et pile = {+, *} .

                           

                           Appuyez sur '*' dans la pile

                           5ème étape : Maintenant, je = 4 et exp[i] = 'c', c'est-à-dire un opérande. Ajoutez ceci dans l'expression postfixe. suffixe = abc et pile = {+, *} .

                           

                           Ajoutez « c » dans le suffixe

                           6ème étape : Maintenant, je = 5 et exp[i] = '+', c'est-à-dire un opérateur. L'élément le plus haut de la pile a une priorité plus élevée. Alors pop jusqu'à ce que la pile soit vide ou que l'élément supérieur ait moins de priorité. '*' est affiché et ajouté dans postfix. Donc suffixe = abc* et pile = {+} .

                           

                           Pop '*' et ajoutez un suffixe

                           Maintenant, l'élément supérieur est ' + ‘ Cela n’a pas non plus moins de priorité. Éclate-le. suffixe = abc*+ .

                           

                           Pop '+' et ajoutez-le dans postfix

                           La pile est maintenant vide. Alors pousse '+' dans la pile. pile = {+} .

                           

                           Appuyez sur « + » dans la pile

                           7ème étape : Maintenant, je = 6 et exp[i] = 'd', c'est-à-dire un opérande. Ajoutez ceci dans l'expression postfixe. suffixe = abc*+d .

                           

                           Ajoutez « d » dans le suffixe

                           Dernière étape: Il ne reste plus aucun élément. Videz donc la pile et ajoutez-la dans l'expression postfix. suffixe = abc*+d+ .

                           

                           Pop '+' et ajoutez-le dans postfix

                           Vous trouverez ci-dessous l'implémentation de l'algorithme ci-dessus :

                           C

                           #include  #include  #include  // Function to return precedence of operators int prec(char c)  c == '-')  return 1;  else  return -1;  // Function to return associativity of operators char associativity(char c) {  if (c == '^')  return 'R';  return 'L'; // Default to left-associative } // The main function to convert infix expression to postfix expression void infixToPostfix(char s[]) {  char result[1000];  int resultIndex = 0;  int len = strlen(s);  char stack[1000];  int stackIndex = -1;  for (int i = 0; i < len; i++) {  char c = s[i];  // If the scanned character is an operand, add it to the output string.  if ((c>= 'a' && c<= 'z') || (c>= 'A' && c<= 'Z') || (c>= '0' &&c<= '9')) {  result[resultIndex++] = c;  }  // If the scanned character is an ‘(‘, push it to the stack.  else if (c == '(') {  stack[++stackIndex] = c;  }  // If the scanned character is an ‘)’, pop and add to the output string from the stack  // until an ‘(‘ is encountered.  else if (c == ')') {  while (stackIndex>= 0 && stack[stackIndex] != '(') { result[resultIndex++] = stack[stackIndex--];  } stackIndex--; // Pop '(' } // Si un opérateur est analysé else { while (stackIndex>= 0 && (prec(s[i])< prec(stack[stackIndex]) ||  prec(s[i]) == prec(stack[stackIndex]) &&  associativity(s[i]) == 'L')) {  result[resultIndex++] = stack[stackIndex--];  }  stack[++stackIndex] = c;  }  }  // Pop all the remaining elements from the stack  while (stackIndex>= 0) { result[resultIndex++] = stack[stackIndex--];  } résultat[indexrésultat] = ' ';  printf('%s
                           ', résultat); } // Code du pilote int main() { char exp[] = 'a+b*(c^d-e)^(f+g*h)-i';  // Appel de fonction infixToPostfix(exp);  renvoie 0 ; }>

                           Java

                           import java.util.Stack; public class InfixToPostfix {  // Function to return precedence of operators  static int prec(char c)   // Function to return associativity of operators  static char associativity(char c) {  if (c == '^')  return 'R';  return 'L'; // Default to left-associative  }  // The main function to convert infix expression to postfix expression  static void infixToPostfix(String s) {  StringBuilder result = new StringBuilder();  Stackpile = nouvelle pile();  pour (int je = 0; je< s.length(); i++) {  char c = s.charAt(i);  // If the scanned character is an operand, add it to the output string.  if ((c>= 'a' && c<= 'z') || (c>= 'A' && c<= 'Z') || (c>= '0' &&c<= '9')) {  result.append(c);  }  // If the scanned character is an ‘(‘, push it to the stack.  else if (c == '(') {  stack.push(c);  }  // If the scanned character is an ‘)’, pop and add to the output string from the stack  // until an ‘(‘ is encountered.  else if (c == ')') {  while (!stack.isEmpty() && stack.peek() != '(') {  result.append(stack.pop());  }  stack.pop(); // Pop '('  }  // If an operator is scanned  else {  while (!stack.isEmpty() && (prec(s.charAt(i)) < prec(stack.peek()) ||  prec(s.charAt(i)) == prec(stack.peek()) &&  associativity(s.charAt(i)) == 'L')) {  result.append(stack.pop());  }  stack.push(c);  }  }  // Pop all the remaining elements from the stack  while (!stack.isEmpty()) {  result.append(stack.pop());  }  System.out.println(result);  }  // Driver code  public static void main(String[] args) {  String exp = 'a+b*(c^d-e)^(f+g*h)-i';  // Function call  infixToPostfix(exp);  } }>

                           Python

                           def prec(c): if c == '^': return 3 elif c == '/' or c == '*': return 2 elif c == '+' or c == '-': return 1 else: return -1 def associativity(c): if c == '^': return 'R' return 'L' # Default to left-associative def infix_to_postfix(s): result = [] stack = [] for i in range(len(s)): c = s[i] # If the scanned character is an operand, add it to the output string. if ('a' <= c <= 'z') or ('A' <= c <= 'Z') or ('0' <= c <= '9'): result.append(c) # If the scanned character is an ‘(‘, push it to the stack. elif c == '(': stack.append(c) # If the scanned character is an ‘)’, pop and add to the output string from the stack # until an ‘(‘ is encountered. elif c == ')': while stack and stack[-1] != '(': result.append(stack.pop()) stack.pop() # Pop '(' # If an operator is scanned else: while stack and (prec(s[i]) < prec(stack[-1]) or (prec(s[i]) == prec(stack[-1]) and associativity(s[i]) == 'L')): result.append(stack.pop()) stack.append(c) # Pop all the remaining elements from the stack while stack: result.append(stack.pop()) print(''.join(result)) # Driver code exp = 'a+b*(c^d-e)^(f+g*h)-i' # Function call infix_to_postfix(exp)>

                           C#

                           using System; using System.Collections.Generic; class Program {  // Function to return precedence of operators  static int Prec(char c)   c == '*')  return 2;  else if (c == '+'   // Function to return associativity of operators  static char Associativity(char c)  {  if (c == '^')  return 'R';  return 'L'; // Default to left-associative  }  // The main function to convert infix expression to postfix expression  static void InfixToPostfix(string s)  {  Stackpile = nouvelle pile();  Listerésultat = nouvelle liste();  pour (int je = 0; je< s.Length; i++)  {  char c = s[i];  // If the scanned character is an operand, add it to the output string.  if ((c>= 'a' && c<= 'z') || (c>= 'A' && c<= 'Z') || (c>= '0' &&c<= '9'))  {  result.Add(c);  }  // If the scanned character is an ‘(‘, push it to the stack.  else if (c == '(')  {  stack.Push(c);  }  // If the scanned character is an ‘)’, pop and add to the output string from the stack  // until an ‘(‘ is encountered.  else if (c == ')')  {  while (stack.Count>0 && stack.Peek() != '(') { result.Add(stack.Pop());  } stack.Pop(); // Pop '(' } // Si un opérateur est analysé else { while (stack.Count> 0 && (Prec(s[i])< Prec(stack.Peek()) ||  Prec(s[i]) == Prec(stack.Peek()) &&  Associativity(s[i]) == 'L'))  {  result.Add(stack.Pop());  }  stack.Push(c);  }  }  // Pop all the remaining elements from the stack  while (stack.Count>0) { résultat.Add(stack.Pop());  } Console.WriteLine(string.Join('', résultat));  } // Code du pilote static void Main() { string exp = 'a+b*(c^d-e)^(f+g*h)-i';  // Appel de fonction InfixToPostfix(exp);  } }>

                           Javascript

                            /* Javascript implementation to convert  infix expression to postfix*/    //Function to return precedence of operators  function prec(c)  c == '-')  return 1;  else  return -1;    // The main function to convert infix expression  //to postfix expression  function infixToPostfix(s) {  let st = []; //For stack operations, we are using JavaScript built in stack  let result = '';  for(let i = 0; i < s.length; i++) {  let c = s[i];  // If the scanned character is  // an operand, add it to output string.  if((c>= 'a' && c<= 'z') || (c>= 'A' && c<= 'Z') || (c>= '0' &&c<= '9'))  result += c;  // If the scanned character is an  // ‘(‘, push it to the stack.  else if(c == '(')  st.push('(');  // If the scanned character is an ‘)’,  // pop and to output string from the stack  // until an ‘(‘ is encountered.  else if(c == ')') {  while(st[st.length - 1] != '(')  {  result += st[st.length - 1];  st.pop();  }  st.pop();  }  //If an operator is scanned  else {  while(st.length != 0 && prec(s[i]) <= prec(st[st.length - 1])) {  result += st[st.length - 1];  st.pop();   }  st.push(c);  }  }  // Pop all the remaining elements from the stack  while(st.length != 0) {  result += st[st.length - 1];  st.pop();  }  console.log(result + '');  }    let exp = 'a+b*(c^d-e)^(f+g*h)-i';  infixToPostfix(exp); // This code is contributed by decode2207.>

                           C++14

                           #include  using namespace std; // Function to return precedence of operators int prec(char c)  c == '*')  return 2;  else if (c == '+'  // Function to return associativity of operators char associativity(char c) {  if (c == '^')  return 'R';  return 'L'; // Default to left-associative } // The main function to convert infix expression // to postfix expression void infixToPostfix(string s) {  stackSt;  résultat de chaîne ;  pour (int je = 0; je< s.length(); i++) {  char c = s[i];  // If the scanned character is  // an operand, add it to the output string.  if ((c>= 'a' && c<= 'z') || (c>= 'A' && c<= 'Z') || (c>= '0' &&c<= '9'))  result += c;  // If the scanned character is an  // ‘(‘, push it to the stack.  else if (c == '(')  st.push('(');  // If the scanned character is an ‘)’,  // pop and add to the output string from the stack  // until an ‘(‘ is encountered.  else if (c == ')') {  while (st.top() != '(') {  result += st.top();  st.pop();  }  st.pop(); // Pop '('  }  // If an operator is scanned  else {  while (!st.empty() && prec(s[i]) < prec(st.top()) ||  !st.empty() && prec(s[i]) == prec(st.top()) &&  associativity(s[i]) == 'L') {  result += st.top();  st.pop();  }  st.push(c);  }  }  // Pop all the remaining elements from the stack  while (!st.empty()) {  result += st.top();  st.pop();  }  cout << result << endl; } // Driver code int main() {  string exp = 'a+b*(c^d-e)^(f+g*h)-i';  // Function call  infixToPostfix(exp);  return 0; }>

                           
                           Sortir

                           abcd^e-fgh*+^*+i->

                           Complexité temporelle : O(N), où N est la taille de l'expression infixe
                           Espace auxiliaire : O(N), où N est la taille de l'expression infixe