Conversión de Postfijo a Prefijo

Sufijo : una expresión se denomina expresión sufijo si el operador aparece en la expresión después de los operandos. Simplemente de la forma (operando1 operando2 operador). 
Ejemplo : AB+CD-* (Infijo : (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 Postfijo, conviértala en una expresión Prefijo. 
La conversión de la expresión Postfix directamente a Prefix sin pasar por el proceso de convertirlos primero a Infix y luego a Prefix es mucho mejor en términos de cálculo y una mejor comprensión de la expresión (las computadoras evalúan usando la expresión Postfix). 

Ejemplos: 

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

Input :  Postfix : ABC/-AK/L-*
Output : Prefix :  *-A/BC-/AKL
Explanation : Postfix to Infix : ((A-(B/C))*((A/K)-L))
              Infix to Prefix :  *-A/BC-/AKL 

Algoritmo para Postfijo a Prefijo : 
 

• Lea la expresión Postfix de izquierda a derecha
• 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 anterior a ellos. 
  string = operador + operando2 + operando1 
  Y empujar la string resultante de vuelta a Stack
• Repita los pasos anteriores hasta el final de la expresión Postfix.

 A continuación se muestra la implementación de la idea anterior:

// CPP Program to convert postfix to prefix
#include <bits/stdc++.h>
using namespace std;
 
// function to check if character is operator or not
bool isOperator(char x)
{
    switch (x) {
    case '+':
    case '-':
    case '/':
    case '*':
        return true;
    }
    return false;
}
 
// Convert postfix to Prefix expression
string postToPre(string post_exp)
{
    stack<string> s;
 
    // length of expression
    int length = post_exp.size();
 
    // reading from right to left
    for (int i = 0; i < length; i++) {
 
        // check if symbol is operator
        if (isOperator(post_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 = post_exp[i] + op2 + op1;
 
            // 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, post_exp[i]));
        }
    }
 
    string ans = "";
    while (!s.empty()) {
        ans += s.top();
        s.pop();
    }
    return ans;
}
 
// Driver Code
int main()
{
    string post_exp = "ABC/-AK/L-*";
 
    // Function call
    cout << "Prefix : " << postToPre(post_exp);
    return 0;
}

// Java Program to convert postfix to prefix
import java.util.*;
 
class GFG {
 
    // function to check if character
    // is operator or not
    static boolean isOperator(char x)
    {
 
        switch (x) {
        case '+':
        case '-':
        case '/':
        case '*':
            return true;
        }
        return false;
    }
 
    // Convert postfix to Prefix expression
    static String postToPre(String post_exp)
    {
        Stack<String> s = new Stack<String>();
 
        // length of expression
        int length = post_exp.length();
 
        // reading from right to left
        for (int i = 0; i < length; i++) {
 
            // check if symbol is operator
            if (isOperator(post_exp.charAt(i))) {
 
                // pop two operands from stack
                String op1 = s.peek();
                s.pop();
                String op2 = s.peek();
                s.pop();
 
                // concat the operands and operator
                String temp
                    = post_exp.charAt(i) + op2 + op1;
 
                // Push String temp back to stack
                s.push(temp);
            }
 
            // if symbol is an operand
            else {
 
                // push the operand to the stack
                s.push(post_exp.charAt(i) + "");
            }
        }
 
        // concatenate all strings in stack and return the
        // answer
        String ans = "";
        for (String i : s)
            ans += i;
        return ans;
    }
 
    // Driver Code
    public static void main(String args[])
    {
        String post_exp = "ABC/-AK/L-*";
 
        // Function call
        System.out.println("Prefix : "
                           + postToPre(post_exp));
    }
}
 
// This code is contributed by Arnab Kundu

# Python3 Program to convert postfix to prefix
 
# function to check if
# character is operator or not
 
 
def isOperator(x):
 
    if x == "+":
        return True
 
    if x == "-":
        return True
 
    if x == "/":
        return True
 
    if x == "*":
        return True
 
    return False
 
# Convert postfix to Prefix expression
 
 
def postToPre(post_exp):
 
    s = []
 
    # length of expression
    length = len(post_exp)
 
    # reading from right to left
    for i in range(length):
 
        # check if symbol is operator
        if (isOperator(post_exp[i])):
 
            # pop two operands from stack
            op1 = s[-1]
            s.pop()
            op2 = s[-1]
            s.pop()
 
            # concat the operands and operator
            temp = post_exp[i] + op2 + op1
 
            # Push string temp back to stack
            s.append(temp)
 
        # if symbol is an operand
        else:
 
            # push the operand to the stack
            s.append(post_exp[i])
 
    
    ans = ""
    for i in s:
        ans += i
    return ans
 
 
# Driver Code
if __name__ == "__main__":
 
    post_exp = "AB+CD-"
     
    # Function call
    print("Prefix : ", postToPre(post_exp))
 
# This code is contributed by AnkitRai01

// C# Program to convert postfix to prefix
using System;
using System.Collections;
 
class GFG {
 
    // function to check if character
    // is operator or not
    static Boolean isOperator(char x)
    {
 
        switch (x) {
        case '+':
        case '-':
        case '/':
        case '*':
            return true;
        }
        return false;
    }
 
    // Convert postfix to Prefix expression
    static String postToPre(String post_exp)
    {
        Stack s = new Stack();
 
        // length of expression
        int length = post_exp.Length;
 
        // reading from right to left
        for (int i = 0; i < length; i++) {
 
            // check if symbol is operator
            if (isOperator(post_exp[i])) {
 
                // Pop two operands from stack
                String op1 = (String)s.Peek();
                s.Pop();
                String op2 = (String)s.Peek();
                s.Pop();
 
                // concat the operands and operator
                String temp = post_exp[i] + op2 + op1;
 
                // Push String temp back to stack
                s.Push(temp);
            }
 
            // if symbol is an operand
            else {
 
                // Push the operand to the stack
                s.Push(post_exp[i] + "");
            }
        }
 
        String ans = "";
        while (s.Count > 0)
            ans += s.Pop();
        return ans;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        String post_exp = "ABC/-AK/L-*";
       
        // Function call
        Console.WriteLine("Prefix : "
                          + postToPre(post_exp));
    }
}
 
// This code is contributed by Arnab Kundu

<script>
    // Javascript Program to convert postfix to prefix
     
    // function to check if character
    // is operator or not
    function isOperator(x)
    {
  
        switch (x) {
        case '+':
        case '-':
        case '/':
        case '*':
            return true;
        }
        return false;
    }
  
    // Convert postfix to Prefix expression
    function postToPre(post_exp)
    {
        let s = [];
  
        // length of expression
        let length = post_exp.length;
  
        // reading from right to left
        for (let i = 0; i < length; i++) {
  
            // check if symbol is operator
            if (isOperator(post_exp[i])) {
  
                // Pop two operands from stack
                let op1 = s[s.length - 1];
                s.pop();
                let op2 = s[s.length - 1];
                s.pop();
  
                // concat the operands and operator
                let temp = post_exp[i] + op2 + op1;
  
                // Push String temp back to stack
                s.push(temp);
            }
  
            // if symbol is an operand
            else {
  
                // Push the operand to the stack
                s.push(post_exp[i] + "");
            }
        }
  
        let ans = "";
        while (s.length > 0)
            ans += s.pop();
        return ans;
    }
     
    let post_exp = "ABC/-AK/L-*";
        
    // Function call
    document.write("Prefix : " + postToPre(post_exp));
     
    // This code is contributed by suresh07.
</script>

Prefix : *-A/BC-/AKL

Complejidad de tiempo: O(N) donde N es la longitud de la string

Espacio auxiliar: O(N) donde N es el tamaño de la pila.