Escriba un programa para convertir una expresión infija a forma postfija.

Expresión infija: La expresión de la forma a operador b (a + b), es decir, cuando un operador está entre cada par de operandos.
Expresión sufijo: La expresión de la forma a b operador (ab+), es decir, cuando cada par de operandos va seguido de un operador.

Ejemplos:

Aporte: A+B*C+D
Producción: ABC*+D+

Aporte: ((A + B) – C * (D / E)) + F
Producción: AB+CDE/*-F+

¿Por qué la representación con sufijo de la expresión?

El compilador escanea la expresión de izquierda a derecha o de derecha a izquierda.
Considere la expresión: a+b*c+d

• El compilador primero escanea la expresión para evaluar la expresión b * c, luego escanea nuevamente la expresión para agregarle a.
• Luego, el resultado se agrega a d después de otro escaneo.

El escaneo repetido lo hace muy ineficiente. Las expresiones infijas son fácilmente legibles y solucionables por los humanos, mientras que la computadora no puede diferenciar fácilmente los operadores y los paréntesis, por lo que es mejor convertir la expresión a la forma postfija (o prefijo) antes de la evaluación.

La expresión correspondiente en forma de sufijo es abc*+d+ . Las expresiones postfix se pueden evaluar fácilmente usando una pila.

¿Cómo convertir una expresión Infija a una expresión Postfija?

Para convertir una expresión infija en una expresión postfija, utilice el A continuación se detallan los pasos para implementar la idea anterior:

1. Escanea la expresión infija de izquierda a derecha .

2. A continuación se detallan los pasos para implementar la idea anterior:
   1. Si el carácter escaneado es un operando, colóquelo en la expresión postfija.
   3. A continuación se detallan los pasos para implementar la idea anterior:
      1. De lo contrario, haga lo siguiente
         • Si la precedencia y asociatividad del operador escaneado son mayores que la precedencia y asociatividad del operador en la pila [o la pila está vacía o la pila contiene un ' ( ' ], luego empújelo en la pila. [' ^ 'el operador es asociativo correcto y otros operadores como' + ‘,’ – ‘,’ * ' y ' / 'son asociativos de izquierda].
           • Verifique especialmente una condición en la que el operador en la parte superior de la pila y el operador escaneado estén ambos ' ^ '. En esta condición, la precedencia del operador escaneado es mayor debido a su asociatividad derecha. Por lo tanto, será empujado a la pila del operador.
           • En todos los demás casos, cuando la parte superior de la pila de operadores es la misma que la del operador escaneado, saque el operador de la pila debido a la asociatividad izquierda, por lo que el operador escaneado tiene menos prioridad.
         • De lo contrario, extraiga todos los operadores de la pila que tengan mayor o igual prioridad que la del operador escaneado.
           • Después de hacer eso, empuje al operador escaneado hacia la pila. (Si encuentra paréntesis mientras abre, deténgase allí y empuje el operador escaneado en la pila).
      4. A continuación se detallan los pasos para implementar la idea anterior:
         1. Si el carácter escaneado es un ' ( ', empújalo a la pila.
         5. A continuación se detallan los pasos para implementar la idea anterior:
            1. Si el carácter escaneado es un ' ) ', abre la pila y envíala hasta que aparezca ' ( 'se encuentra y descarte ambos paréntesis.
            6. A continuación se detallan los pasos para implementar la idea anterior:
               1. Repita los pasos 2-5 hasta que se escanee la expresión infija.
               7. A continuación se detallan los pasos para implementar la idea anterior:

                  base de datos

                  1. Una vez finalizado el escaneo, abra la pila y agregue los operadores en la expresión postfija hasta que no esté vacía.
                  8. A continuación se detallan los pasos para implementar la idea anterior:
                     1. Finalmente, imprima la expresión postfix.

                     A continuación se detallan los pasos para implementar la idea anterior:

                     1. Ilustración:

                     A continuación se detallan los pasos para implementar la idea anterior:

                     1. Siga la siguiente ilustración para una mejor comprensión.
                        A continuación se detallan los pasos para implementar la idea anterior:

                        1. Considere la expresión infija exp = a+b*c+d
                           y la expresión infija se escanea usando el iterador i , que se inicializa como yo = 0 .

                           1er paso: Aquí i = 0 y exp[i] = 'a', es decir, un operando. Entonces agregue esto en la expresión postfix. Por lo tanto, sufijo = a .

                           

                           Agregue 'a' en el sufijo

                           2do paso: Aquí i = 1 y exp[i] = '+' es decir, un operador. Empuje esto hacia la pila. sufijo = a y pila = {+} .

                           

                           Empuje '+' en la pila

                           3er paso: Ahora i = 2 y exp[i] = 'b' es decir, un operando. Entonces agregue esto en la expresión postfix. sufijo = ab y pila = {+} .

                           

                           Agregue 'b' en el sufijo

                           4to paso: Ahora i = 3 y exp[i] = '*' es decir, un operador. Empuje esto hacia la pila. sufijo = ab y pila = {+, *} .

                           

                           Empuje '*' en la pila

                           5to paso: Ahora i = 4 y exp[i] = 'c' es decir, un operando. Agregue esto en la expresión postfix. sufijo = abc y pila = {+, *} .

                           

                           Agregue 'c' en el sufijo

                           6to paso: Ahora i = 5 y exp[i] = '+' es decir, un operador. El elemento superior de la pila tiene mayor prioridad. Así que pop hasta que la pila quede vacía o el elemento superior tenga menos prioridad. '*' aparece y se agrega en postfix. Entonces sufijo = abc* y pila = {+} .

                           

                           Pop '*' y agregue postfix

                           Ahora el elemento superior es ' + 'Eso tampoco tiene menos precedencia. Pop it. sufijo = abc*+ .

                           

                           Haga clic en '+' y agréguelo en postfix.

                           Ahora la pila está vacía. Así que empuja ‘+’ en la pila. pila = {+} .

                           

                           Empuje '+' en la pila

                           7mo paso: Ahora i = 6 y exp[i] = 'd' es decir, un operando. Agregue esto en la expresión postfix. sufijo = abc*+d .

                           

                           Agregue 'd' en el sufijo

                           Último paso: Ahora no queda ningún elemento. Así que vacíe la pila y agréguela en la expresión postfix. sufijo = abc*+d+ .

                           

                           Haga clic en '+' y agréguelo en postfix.

                           A continuación se muestra la implementación del algoritmo 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 && pila[stackIndex] != '(') { resultado[resultIndex++] = pila[stackIndex--];  } stackIndex--; // Pop '(' } // Si se escanea 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) { resultado[resultIndex++] = pila[stackIndex--];  } resultado[resultIndex] = ' ';  printf('%s
                           ', resultado); } // Código del controlador int main() { char exp[] = 'a+b*(c^d-e)^(f+g*h)-i';  // Llamada a función infixToPostfix(exp);  devolver 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();  Stackpila = nueva pila();  para (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);  } }>

                           Pitón

                           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 = nueva pila();  Listaresultado = nueva lista();  para (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 && pila.Peek() != '(') { resultado.Add(stack.Pop());  } pila.Pop(); // Pop '(' } // Si se escanea 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) { resultado.Add(stack.Pop());  } Console.WriteLine(string.Join('', resultado));  } // Código del controlador static void Main() { string exp = 'a+b*(c^d-e)^(f+g*h)-i';  // Llamada a función 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) {  stackcalle;  resultado de cadena;  para (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; }>

                           
                           Producción

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

                           Complejidad del tiempo: O(N), donde N es el tamaño de la expresión infija
                           Espacio Auxiliar: O(N), donde N es el tamaño de la expresión infija