Escriu un programa per convertir una expressió Infix a un formulari Postfix.

Expressió infixa: L'expressió de la forma a operador b (a + b), és a dir, quan un operador es troba entre cada parell d'operands.
Expressió postfix: L'expressió de l'operador de forma a b (ab+), és a dir, quan cada parell d'operands va seguit d'un operador.

Exemples:

Entrada: A + B * C + D
Sortida: ABC*+D+

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

Per què representació postfixa de l'expressió?

El compilador explora l'expressió d'esquerra a dreta o de dreta a esquerra.
Considereu l'expressió: a + b * c + d

• El compilador escaneja primer l'expressió per avaluar l'expressió b * c, després torna a escanejar l'expressió per afegir-hi a.
• El resultat s'afegeix a d després d'una altra exploració.

L'escaneig repetit el fa molt ineficient. Les expressions infixes són fàcilment llegibles i solucionables pels humans, mentre que l'ordinador no pot diferenciar fàcilment els operadors i els parèntesis, per tant, és millor convertir l'expressió a la forma postfix (o prefix) abans de l'avaluació.

L'expressió corresponent en forma de postfix és abc*+d+ . Les expressions postfix es poden avaluar fàcilment mitjançant una pila.

Com convertir una expressió Infix en una expressió Postfix?

Per convertir una expressió infixa en una expressió postfixa, utilitzeu A continuació es mostren els passos per implementar la idea anterior:

1. Escaneja l'expressió infixa d'esquerra a dreta .

2. A continuació es mostren els passos per implementar la idea anterior:
   1. Si el caràcter escanejat és un operand, poseu-lo a l'expressió postfix.
   3. A continuació es mostren els passos per implementar la idea anterior:
      1. En cas contrari, feu el següent
         • Si la precedència i l'associativitat de l'operador escanejat són més grans que la precedència i l'associativitat de l'operador a la pila [o la pila està buida o la pila conté un ' ( ' ] i, a continuació, empènyer-lo a la pila. [' ^ 'l'operador té raó associatiu i altres operadors com' + ‘,’ – ‘,’ * 'i' / 'són associatius d'esquerra].
           • Comproveu especialment si hi ha una condició en què l'operador a la part superior de la pila i l'operador escanejat són tots dos ' ^ ‘. En aquesta condició, la precedència de l'operador escanejat és més alta per la seva dreta associativitat. Per tant, s'empeny a la pila d'operadors.
           • En tots els altres casos, quan la part superior de la pila d'operadors és la mateixa que l'operador escanejat, aleshores traieu l'operador de la pila a causa de l'associativitat de l'esquerra a causa de la qual l'operador escanejat té menys preferència.
         • En cas contrari, esclaten tots els operadors de la pila que tinguin prioritat superior o igual a la de l'operador escanejat.
           • Després de fer-ho, premeu l'operador escanejat a la pila. (Si trobeu un parèntesi mentre apareix, atureu-vos allà i premeu l'operador escanejat a la pila.)
      4. A continuació es mostren els passos per implementar la idea anterior:
         1. Si el caràcter escanejat és un ' ( ', empènyer-lo a la pila.
         5. A continuació es mostren els passos per implementar la idea anterior:
            1. Si el caràcter escanejat és un ' ) ’, desplega la pila i emet-la fins que un ‘ ( ' es troba i descarta els dos parèntesis.
            6. A continuació es mostren els passos per implementar la idea anterior:
               1. Repetiu els passos 2-5 fins que s'escanegi l'expressió infixa.
               7. A continuació es mostren els passos per implementar la idea anterior:

                  java cast char a cadena

                  1. Un cop finalitzada l'escaneig, desplegueu la pila i afegiu els operadors a l'expressió postfix fins que no estigui buida.
                  8. A continuació es mostren els passos per implementar la idea anterior:
                     1. Finalment, imprimiu l'expressió postfix.

                     A continuació es mostren els passos per implementar la idea anterior:

                     1. Il·lustració:

                     A continuació es mostren els passos per implementar la idea anterior:

                     1. Seguiu la il·lustració següent per a una millor comprensió
                        A continuació es mostren els passos per implementar la idea anterior:

                        1. Considereu l'expressió infixa exp = a+b*c+d
                           i l'expressió infixa s'escaneja mitjançant l'iterador i , que s'inicia com a i = 0 .

                           1r pas: Aquí i = 0 i exp[i] = 'a', és a dir, un operand. Així que afegiu això a l'expressió postfix. Per tant, postfix = a .

                           

                           Afegeix 'a' al postfix

                           2n pas: Aquí i = 1 i exp[i] = '+', és a dir, un operador. Empeny això a la pila. postfix = a i pila = {+} .

                           

                           Premeu '+' a la pila

                           3r pas: Ara i = 2 i exp[i] = 'b', és a dir, un operand. Així que afegiu això a l'expressió postfix. postfix = ab i pila = {+} .

                           

                           Afegeix 'b' al postfix

                           4t pas: Ara i = 3 i exp[i] = '*', és a dir, un operador. Empeny això a la pila. postfix = ab i pila = {+, *} .

                           

                           Premeu '*' a la pila

                           5è pas: Ara i = 4 i exp[i] = 'c', és a dir, un operand. Afegiu-ho a l'expressió postfix. postfix = abc i pila = {+, *} .

                           

                           Afegeix 'c' al postfix

                           6è pas: Ara i = 5 i exp[i] = '+', és a dir, un operador. L'element superior de la pila té una prioritat més alta. Així que obre fins que la pila quedi buida o l'element superior tingui menys preferència. '*' apareix i s'afegeix al postfix. Tan postfix = abc* i pila = {+} .

                           

                           Feu clic a '*' i afegiu-hi postfix

                           Ara l'element superior és ' + ‘Això tampoc té menys preferència. Pop-ho. postfix = abc*+ .

                           

                           Feu clic a '+' i afegiu-lo al postfix

                           Ara la pila està buida. Així que empeny ‘+’ a la pila. pila = {+} .

                           

                           Premeu '+' a la pila

                           7è pas: Ara i = 6 i exp[i] = 'd', és a dir, un operand. Afegiu-ho a l'expressió postfix. postfix = abc*+d .

                           

                           Afegeix 'd' al postfix

                           Pas final: Ara no queda cap element. Així que buideu la pila i afegiu-la a l'expressió postfix. postfix = abc*+d+ .

                           

                           Feu clic a '+' i afegiu-lo al postfix

                           A continuació es mostra la implementació de l'algorisme anterior:

                           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] != '(') { resultat[resultIndex++] = stack[stackIndex--];  } stackIndex--; // Pop '(' } // Si s'escaneja un operador 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) { resultat[resultIndex++] = pila[stackIndex--];  } resultat[resultatIndex] = ' ';  printf('%s
                           ', resultat); } // Codi del controlador int main() { char exp[] = 'a+b*(c^d-e)^(f+g*h)-i';  // Crida a la funció infixToPostfix(exp);  retorn 0; }>>>Javapila = nova pila ();  per (int i = 0; i< 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)  {  Stackpila = pila nova();  Llistaresultat = nova llista();  per (int i = 0; i< 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() != '(') { resultat.Add(stack.Pop());  } stack.Pop(); // Pop '(' } // Si s'escaneja un operador 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) { resultat.Add(stack.Pop());  } Console.WriteLine(string.Join('', resultat));  } // Codi del controlador static void Main() { string exp = 'a+b*(c^d-e)^(f+g*h)-i';  // Crida a la funció InfixToPostfix(exp);  } }>>>Javascript= '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;  resultat de la cadena;  per (int i = 0; i< 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; }>

                           
                           Sortida

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

                           Complexitat temporal: O(N), on N és la mida de l'expressió infixa
                           Espai auxiliar: O(N), on N és la mida de l'expressió infixa