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