Conversión de prefijo a sufijo

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) )

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))
Dada una expresión de Prefijo, conviértala en una expresión de Postfijo. 
Conversión de la expresión de Prefijo directamente a Postfijo sin pasar por el proceso de convertirlos primero a Infijo y luego, Postfix 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 :  Prefix :  *+AB-CD
Output : Postfix : AB+CD-*
Explanation : Prefix to Infix :  (A+B) * (C-D)
              Infix to Postfix :  AB+CD-*

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

Algoritmo para Prefijo a Postfijo : 

• 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 que les sigue. 
  string = operando1 + operando2 + operador 
  Y empujar la string resultante de vuelta a Stack
• Repita los pasos anteriores hasta el final de la expresión de prefijo.

// CPP Program to convert prefix to postfix
#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 '*':
        return true;
    }
    return false;
}
 
// Convert prefix to Postfix expression
string preToPost(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 + op2 + pre_exp[i];
 
            // 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 contains only the Postfix expression
    return s.top();
}
 
// Driver Code
int main()
{
    string pre_exp = "*-A/BC-/AKL";
    cout << "Postfix : " << preToPost(pre_exp);
    return 0;
}

// JavaProgram to convert prefix to postfix
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 prefix to Postfix expression
    static String preToPost(String pre_exp)
    {
 
        Stack<String> s = new Stack<String>();
 
        // length of expression
        int length = pre_exp.length();
 
        // reading from right to left
        for (int i = length - 1; i >= 0; i--)
        {
            // check if symbol is operator
            if (isOperator(pre_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 = op1 + op2 + pre_exp.charAt(i);
 
                // Push String temp back to stack
                s.push(temp);
            }
 
            // if symbol is an operand
            else {
                // push the operand to the stack
                s.push(pre_exp.charAt(i) + "");
            }
        }
 
        // stack contains only the Postfix expression
        return s.peek();
    }
 
    // Driver Code
    public static void main(String args[])
    {
        String pre_exp = "*-A/BC-/AKL";
        System.out.println("Postfix : "
                           + preToPost(pre_exp));
    }
}
 
// This code is contributed by Arnab Kundu

# Write Python3 code here
# -*- coding: utf-8 -*-
 
# Example Input
s = "*-A/BC-/AKL"
 
# Stack for storing operands
stack = []
 
operators = set(['+', '-', '*', '/', '^'])
 
# Reversing the order
s = s[::-1]
 
# iterating through individual tokens
for i in s:
 
    # if token is operator
    if i in operators:
 
        # pop 2 elements from stack
        a = stack.pop()
        b = stack.pop()
 
        # concatenate them as operand1 +
        # operand2 + operator
        temp = a+b+i
        stack.append(temp)
 
    # else if operand
    else:
        stack.append(i)
 
# printing final output
print(*stack)

// C# Program to convert prefix to postfix
using System;
using System.Collections.Generic;
 
class GFG {
 
    // function to check if character
    // is operator or not
    static bool isOperator(char x)
    {
        switch (x) {
        case '+':
        case '-':
        case '/':
        case '*':
            return true;
        }
        return false;
    }
 
    // Convert prefix to Postfix expression
    static String preToPost(String pre_exp)
    {
 
        Stack<String> s = new Stack<String>();
 
        // length of expression
        int length = pre_exp.Length;
 
        // 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.Peek();
                s.Pop();
                String op2 = s.Peek();
                s.Pop();
 
                // concat the operands and operator
                String temp = op1 + op2 + pre_exp[i];
 
                // Push String temp back to stack
                s.Push(temp);
            }
 
            // if symbol is an operand
            else {
                // push the operand to the stack
                s.Push(pre_exp[i] + "");
            }
        }
 
        // stack contains only the Postfix expression
        return s.Peek();
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        String pre_exp = "*-A/BC-/AKL";
        Console.WriteLine("Postfix : "
                          + preToPost(pre_exp));
    }
}
 
/* This code contributed by PrinciRaj1992 */

<script>
    // Javascript Program to convert prefix to postfix
     
    // function to check if character
    // is operator or not
    function isOperator(x)
    {
        switch (x) {
        case '+':
        case '-':
        case '/':
        case '*':
            return true;
        }
        return false;
    }
     
    // Convert prefix to Postfix expression
    function preToPost(pre_exp)
    {
  
        let s = [];
  
        // length of expression
        let length = pre_exp.length;
  
        // reading from right to left
        for (let i = length - 1; i >= 0; i--)
        {
  
            // check if symbol is operator
            if (isOperator(pre_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 = op1 + op2 + pre_exp[i];
  
                // Push String temp back to stack
                s.push(temp);
            }
  
            // if symbol is an operand
            else {
                // push the operand to the stack
                s.push(pre_exp[i] + "");
            }
        }
  
        // stack contains only the Postfix expression
        return s[s.length - 1];
    }
     
    let pre_exp = "*-A/BC-/AKL";
    document.write("Postfix : " + preToPost(pre_exp));
     
    // This code is contributed by suresh07.
</script>

Postfix : ABC/-AK/L-*

Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar la expresión.

Espacio auxiliar: O(N), ya que estamos usando stack para espacio extra.