Conversión de prefijo a infijo

Infijo : una expresión se llama expresión infija si el operador aparece entre los operandos en la expresión. Simplemente de la forma (operando1 operador operando2). 
Ejemplo: (A+B) * (CD)

Prefijo : una expresión se llama expresión de prefijo si el operador aparece en la expresión antes de los operandos. Simplemente de la forma (operador operando1 operando2). 
Ejemplo : *+AB-CD (Infijo : (A+B) * (CD) )

Dada una expresión de prefijo, conviértala en una expresión de infijo. 
Las computadoras generalmente hacen el cálculo en prefijo o posfijo (generalmente posfijo). Pero para los humanos, es más fácil entender una expresión Infix que un prefijo. Por lo tanto, la conversión es necesaria para la comprensión humana.

Ejemplos: 

Input :  Prefix :  *+AB-CD
Output : Infix : ((A+B)*(C-D))

Input :  Prefix :  *-A/BC-/AKL
Output : Infix : ((A-(B/C))*((A/K)-L))

Algoritmo para prefijo a infijo

  • Lea la expresión del prefijo en orden inverso (de derecha a izquierda)
  • Si el símbolo es un operando, entonces empújelo a la pila
  • Si el símbolo es un operador, extraiga dos operandos de la pila 
    . Cree una string concatenando los dos operandos y el operador entre ellos. 
    string = (operando1 + operador + operando2) 
    Y empujar la string resultante de vuelta a Stack
  • Repita los pasos anteriores hasta el final de la expresión de prefijo.
  • Al final, la pila tendrá solo 1 string, es decir, la string resultante

C++

// C++ Program to convert prefix to Infix
#include <iostream>
#include <stack>
using namespace std;
 
// function to check if character is operator or not
bool isOperator(char x) {
  switch (x) {
  case '+':
  case '-':
  case '/':
  case '*':
  case '^':
  case '%':
    return true;
  }
  return false;
}
 
// Convert prefix to Infix expression
string preToInfix(string pre_exp) {
  stack<string> s;
 
  // length of expression
  int length = pre_exp.size();
 
  // reading from right to left
  for (int i = length - 1; i >= 0; i--) {
 
    // check if symbol is operator
    if (isOperator(pre_exp[i])) {
 
      // pop two operands from stack
      string op1 = s.top();   s.pop();
      string op2 = s.top();   s.pop();
 
      // concat the operands and operator
      string temp = "(" + op1 + pre_exp[i] + op2 + ")";
 
      // Push string temp back to stack
      s.push(temp);
    }
 
    // if symbol is an operand
    else {
 
      // push the operand to the stack
      s.push(string(1, pre_exp[i]));
    }
  }
 
  // Stack now contains the Infix expression
  return s.top();
}
 
// Driver Code
int main() {
  string pre_exp = "*-A/BC-/AKL";
  cout << "Infix : " << preToInfix(pre_exp);
  return 0;
}

Java

// Java program to convert prefix to Infix
import java.util.Stack;
 
class GFG{
 
// Function to check if character
// is operator or not    
static    boolean isOperator(char x)
{
    switch(x)
    {
        case '+':
        case '-':
        case '*':
        case '/':
        case '^':
        case '%':
            return true;
    }
    return false;
}
 
// Convert prefix to Infix expression
public static String convert(String str)
{
    Stack<String> stack = new Stack<>();
     
    // Length of expression
    int l = str.length();
     
    // Reading from right to left
    for(int i = l - 1; i >= 0; i--)
    {
        char c = str.charAt(i);
        if (isOperator(c))
        {
            String op1 = stack.pop();
            String op2 = stack.pop();
             
            // Concat the operands and operator
            String temp = "(" + op1 + c + op2 + ")";
            stack.push(temp);
        }
        else
        {
             
            // To make character to string
            stack.push(c + "");
        }
    }
    return stack.pop();
}
 
// Driver code
public static void main(String[] args)
{
    String exp = "*-A/BC-/AKL";
    System.out.println("Infix : " + convert(exp));
}
}
 
// This code is contributed by abbeyme

Python3

# Python Program to convert prefix to Infix
def prefixToInfix(prefix):
    stack = []
     
    # read prefix in reverse order
    i = len(prefix) - 1
    while i >= 0:
        if not isOperator(prefix[i]):
             
            # symbol is operand
            stack.append(prefix[i])
            i -= 1
        else:
           
            # symbol is operator
            str = "(" + stack.pop() + prefix[i] + stack.pop() + ")"
            stack.append(str)
            i -= 1
     
    return stack.pop()
 
def isOperator(c):
    if c == "*" or c == "+" or c == "-" or c == "/" or c == "^" or c == "(" or c == ")":
        return True
    else:
        return False
 
# Driver code
if __name__=="__main__":
    str = "*-A/BC-/AKL"
    print(prefixToInfix(str))
     
# This code is contributed by avishekarora

C#

// C# program to convert prefix to Infix
using System;
using System.Collections;
 
class GFG{
  
// Function to check if character
// is operator or not    
static bool isOperator(char x)
{
    switch(x)
    {
        case '+':
        case '-':
        case '*':
        case '/':
        case '^':
        case '%':
            return true;
    }
    return false;
}
  
// Convert prefix to Infix expression
public static string convert(string str)
{
    Stack stack = new Stack();
      
    // Length of expression
    int l = str.Length;
      
    // Reading from right to left
    for(int i = l - 1; i >= 0; i--)
    {
        char c = str[i];
         
        if (isOperator(c))
        {
            string op1 = (string)stack.Pop();
            string op2 = (string)stack.Pop();
              
            // Concat the operands and operator
            string temp = "(" + op1 + c + op2 + ")";
            stack.Push(temp);
        }
        else
        {
             
            // To make character to string
            stack.Push(c + "");
        }
    }
    return (string)stack.Pop();
}
  
// Driver code
public static void Main(string[] args)
{
    string exp = "*-A/BC-/AKL";
     
    Console.Write("Infix : " + convert(exp));
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
    // Javascript program to convert prefix to Infix
     
    // Function to check if character
    // is operator or not   
    function isOperator(x)
    {
        switch(x)
        {
            case '+':
            case '-':
            case '*':
            case '/':
            case '^':
            case '%':
                return true;
        }
        return false;
    }
 
    // Convert prefix to Infix expression
    function convert(str)
    {
        let stack = [];
 
        // Length of expression
        let l = str.length;
 
        // Reading from right to left
        for(let i = l - 1; i >= 0; i--)
        {
            let c = str[i];
 
            if (isOperator(c))
            {
                let op1 = stack[stack.length - 1];
                stack.pop()
                let op2 = stack[stack.length - 1];
                stack.pop()
 
                // Concat the operands and operator
                let temp = "(" + op1 + c + op2 + ")";
                stack.push(temp);
            }
            else
            {
 
                // To make character to string
                stack.push(c + "");
            }
        }
        return stack[stack.length - 1];
    }
     
    let exp = "*-A/BC-/AKL";
      
    document.write("Infix : " + convert(exp));
     
    // This code is contributed by suresh07.
</script>
Producción

Infix : ((A-(B/C))*((A/K)-L))

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(n)

Publicación traducida automáticamente

Artículo escrito por shubham_rana_77 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *