La conversión de la expresión infijo a sufijo se puede hacer elegantemente usando dos funciones de precedencia. A cada operador se le asigna un valor (mayor valor significa mayor precedencia) que depende de si el operador está dentro o fuera de la pila. También la asociatividad derecha e izquierda para diferentes operadores puede manejarse variando sus valores en las dos funciones de precedencia.
Ejemplo de expresión de infijo: a+b*c
Su correspondiente expresión de sufijo : abc*+
Los siguientes pasos explican cómo se ha realizado esta conversión.
Paso 1: a + bc* (Aquí tenemos dos operadores: + y * en los que * tiene mayor precedencia y por lo tanto se evaluará primero).
Paso 2: abc*+ (Ahora nos queda un operador que es + por lo que se evalúa)
Para saber más sobre las expresiones infijo y sufijo , visite los enlaces.
Nota: En este artículo, asumimos que todos los operadores son asociativos de izquierda a derecha.
Ejemplos:
Entrada: str = “a+b*c-(d/e+f*g*h)”
Salida: abc*+de/fg*h*+-Paso 1: a+b*c-(de/+f*g*h)
Paso 2: a+b*c-(de/+fg* *h)
Paso 3: a+b*c-(de/+fg*h*)
Paso 4: a+b*c-(de/fg*h*+)
Paso 5: a+bc*-de/fg*h*+
Paso 6: abc*+-de/fg*h*+
Paso 7: abc*+de/fg*h*+-
Entrada: a+b*c/h
Salida: abc*h/+Paso 1: a+bc*/h
Paso 2: a+bc*h/
Paso 3: abc*h/+
Acercarse:
- Si el carácter de entrada es un operando, imprímalo.
- Si el carácter de entrada es un operador-
- Si la pila está vacía, empújela hacia la pila.
- Si su valor de precedencia es mayor que el valor de precedencia del carácter en la parte superior, empuje.
- Si su valor de precedencia es menor o igual, salte de la pila e imprima, mientras que la precedencia del carácter superior es mayor que el valor de precedencia del carácter de entrada.
- Si el carácter de entrada es ‘)’, extraiga e imprima hasta que la parte superior sea ‘(‘. (Extraiga ‘(‘ pero no lo imprima.)
- Si la pila se vacía antes de encontrar ‘(‘, entonces es una expresión no válida.
- Repita los pasos 1 a 4 hasta que la expresión de entrada se haya leído por completo.
- Extraiga los elementos restantes de la pila e imprímalos.
El método anterior maneja la asociatividad derecha del operador de exponenciación (aquí, ^) asignándole un valor de precedencia más alto fuera de la pila y un valor de precedencia más bajo dentro de la pila, mientras que es opuesto para los operadores asociativos por la izquierda.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to convert an infix expression to a
// postfix expression using two precedence function
#include <bits/stdc++.h>
using namespace std;
// to check if the input character
// is an operator or a '('
int isOperator(char input)
{
switch (input) {
case '+':
return 1;
case '-':
return 1;
case '*':
return 1;
case '%':
return 1;
case '/':
return 1;
case '(':
return 1;
}
return 0;
}
// to check if the input character is an operand
int isOperand(char input)
{
if (input >= 65 && input <= 90
|| input >= 97 && input <= 122)
return 1;
return 0;
}
// function to return precedence value
// if operator is present in stack
int inPrec(char input)
{
switch (input) {
case '+':
case '-':
return 2;
case '*':
case '%':
case '/':
return 4;
case '(':
return 0;
}
}
// function to return precedence value
// if operator is present outside stack.
int outPrec(char input)
{
switch (input) {
case '+':
case '-':
return 1;
case '*':
case '%':
case '/':
return 3;
case '(':
return 100;
}
}
// function to convert infix to postfix
void inToPost(char* input)
{
stack<char> s;
// while input is not NULL iterate
int i = 0;
while (input[i] != '\0') {
// if character an operand
if (isOperand(input[i])) {
printf("%c", input[i]);
}
// if input is an operator, push
else if (isOperator(input[i])) {
if (s.empty()
|| outPrec(input[i]) > inPrec(s.top()))
s.push(input[i]);
else {
while (!s.empty()
&& outPrec(input[i]) < inPrec(s.top())) {
printf("%c", s.top());
s.pop();
}
s.push(input[i]);
}
}
// condition for opening bracket
else if (input[i] == ')') {
while (s.top() != '(') {
printf("%c", s.top());
s.pop();
// if opening bracket not present
if (s.empty()) {
printf("Wrong input\n");
exit(1);
}
}
// pop the opening bracket.
s.pop();
}
i++;
}
// pop the remaining operators
while (!s.empty()) {
if (s.top() == '(') {
printf("\n Wrong input\n");
exit(1);
}
printf("%c", s.top());
s.pop();
}
}
// Driver code
int main()
{
char input[] = "a+b*c-(d/e+f*g*h)";
inToPost(input);
return 0;
}
Java
import static java.lang.System.exit;
import java.util.Stack;
// Java program to convert an infix expression to a
// postfix expression using two precedence function
class GFG {
// to check if the input character
// is an operator or a '('
static int isOperator(char input)
{
switch (input) {
case '+':
return 1;
case '-':
return 1;
case '*':
return 1;
case '%':
return 1;
case '/':
return 1;
case '(':
return 1;
}
return 0;
}
// to check if the input character is an operand
static int isOperand(char input)
{
if (input >= 65 && input <= 90
|| input >= 97 && input <= 122) {
return 1;
}
return 0;
}
// function to return precedence value
// if operator is present in stack
static int inPrec(char input)
{
switch (input) {
case '+':
case '-':
return 2;
case '*':
case '%':
case '/':
return 4;
case '(':
return 0;
}
return 0;
}
// function to return precedence value
// if operator is present outside stack.
static int outPrec(char input)
{
switch (input) {
case '+':
case '-':
return 1;
case '*':
case '%':
case '/':
return 3;
case '(':
return 100;
}
return 0;
}
// function to convert infix to postfix
static void inToPost(char[] input)
{
Stack<Character> s = new Stack<Character>();
// while input is not NULL iterate
int i = 0;
while (input.length != i) {
// if character an operand
if (isOperand(input[i]) == 1) {
System.out.printf("%c", input[i]);
} // if input is an operator, push
else if (isOperator(input[i]) == 1) {
if (s.empty()
|| outPrec(input[i]) > inPrec(s.peek())) {
s.push(input[i]);
}
else {
while (!s.empty()
&& outPrec(input[i]) < inPrec(s.peek())) {
System.out.printf("%c", s.peek());
s.pop();
}
s.push(input[i]);
}
} // condition for opening bracket
else if (input[i] == ')') {
while (s.peek() != '(') {
System.out.printf("%c", s.peek());
s.pop();
// if opening bracket not present
if (s.empty()) {
System.out.printf("Wrong input\n");
exit(1);
}
}
// pop the opening bracket.
s.pop();
}
i++;
}
// pop the remaining operators
while (!s.empty()) {
if (s.peek() == '(') {
System.out.printf("\n Wrong input\n");
exit(1);
}
System.out.printf("%c", s.peek());
s.pop();
}
}
// Driver code
static public void main(String[] args)
{
char input[] = "a+b*c-(d/e+f*g*h)".toCharArray();
inToPost(input);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to convert an infix
# expression to a postfix expression
# using two precedence function
# To check if the input character
# is an operator or a '('
def isOperator(input):
switch = {
'+': 1,
'-': 1,
'*': 1,
'/': 1,
'%': 1,
'(': 1,
}
return switch.get(input, False)
# To check if the input character is an operand
def isOperand(input):
if ((ord(input) >= 65 and ord(input) <= 90) or
(ord(input) >= 97 and ord(input) <= 122)):
return 1
return 0
# Function to return precedence value
# if operator is present in stack
def inPrec(input):
switch = {
'+': 2,
'-': 2,
'*': 4,
'/': 4,
'%': 4,
'(': 0,
}
return switch.get(input, 0)
# Function to return precedence value
# if operator is present outside stack.
def outPrec(input):
switch = {
'+': 1,
'-': 1,
'*': 3,
'/': 3,
'%': 3,
'(': 100,
}
return switch.get(input, 0)
# Function to convert infix to postfix
def inToPost(input):
i = 0
s = []
# While input is not NULL iterate
while (len(input) != i):
# If character an operand
if (isOperand(input[i]) == 1):
print(input[i], end = "")
# If input is an operator, push
elif (isOperator(input[i]) == 1):
if (len(s) == 0 or
outPrec(input[i]) >
inPrec(s[-1])):
s.append(input[i])
else:
while(len(s) > 0 and
outPrec(input[i]) <
inPrec(s[-1])):
print(s[-1], end = "")
s.pop()
s.append(input[i])
# Condition for opening bracket
elif(input[i] == ')'):
while(s[-1] != '('):
print(s[-1], end = "")
s.pop()
# If opening bracket not present
if(len(s) == 0):
print('Wrong input')
exit(1)
# pop the opening bracket.
s.pop()
i += 1
# pop the remaining operators
while(len(s) > 0):
if(s[-1] == '('):
print('Wrong input')
exit(1)
print(s[-1], end = "")
s.pop()
# Driver code
input = "a+b*c-(d/e+f*g*h)"
inToPost(input)
# This code is contributed by dheeraj_2801
C#
// C# program to convert an infix expression to a
// postfix expression using two precedence function
using System.Collections.Generic;
using System;
public class GFG {
// to check if the input character
// is an operator or a '('
static int isOperator(char input)
{
switch (input) {
case '+':
return 1;
case '-':
return 1;
case '*':
return 1;
case '%':
return 1;
case '/':
return 1;
case '(':
return 1;
}
return 0;
}
// to check if the input character is an operand
static int isOperand(char input)
{
if (input >= 65 && input <= 90
|| input >= 97 && input <= 122) {
return 1;
}
return 0;
}
// function to return precedence value
// if operator is present in stack
static int inPrec(char input)
{
switch (input) {
case '+':
case '-':
return 2;
case '*':
case '%':
case '/':
return 4;
case '(':
return 0;
}
return 0;
}
// function to return precedence value
// if operator is present outside stack.
static int outPrec(char input)
{
switch (input) {
case '+':
case '-':
return 1;
case '*':
case '%':
case '/':
return 3;
case '(':
return 100;
}
return 0;
}
// function to convert infix to postfix
static void inToPost(char[] input)
{
Stack<char> s = new Stack<char>();
// while input is not NULL iterate
int i = 0;
while (input.Length != i) {
// if character an operand
if (isOperand(input[i]) == 1) {
Console.Write(input[i]);
}
// if input is an operator, push
else if (isOperator(input[i]) == 1) {
if (s.Count == 0
|| outPrec(input[i]) > inPrec(s.Peek())) {
s.Push(input[i]);
}
else {
while (s.Count != 0
&& outPrec(input[i]) < inPrec(s.Peek())) {
Console.Write(s.Peek());
s.Pop();
}
s.Push(input[i]);
}
} // condition for opening bracket
else if (input[i] == ')') {
while (s.Peek() != '(') {
Console.Write(s.Peek());
s.Pop();
// if opening bracket not present
if (s.Count == 0) {
Console.Write("Wrong input\n");
return;
}
}
// pop the opening bracket.
s.Pop();
}
i++;
}
// pop the remaining operators
while (s.Count != 0) {
if (s.Peek() == '(') {
Console.Write("\n Wrong input\n");
return;
}
Console.Write(s.Peek());
s.Pop();
}
}
// Driver code
static public void Main()
{
char[] input = "a+b*c-(d/e+f*g*h)".ToCharArray();
inToPost(input);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to convert an infix expression to a
// postfix expression using two precedence function
// to check if the input character
// is an operator or a '('
function isOperator(input)
{
switch (input) {
case '+':
return 1;
case '-':
return 1;
case '*':
return 1;
case '%':
return 1;
case '/':
return 1;
case '(':
return 1;
}
return 0;
}
// to check if the input character is an operand
function isOperand(input)
{
if (input.charCodeAt() >= 65 && input.charCodeAt() <= 90
|| input.charCodeAt() >= 97 && input.charCodeAt() <= 122) {
return 1;
}
return 0;
}
// function to return precedence value
// if operator is present in stack
function inPrec(input)
{
switch (input) {
case '+':
case '-':
return 2;
case '*':
case '%':
case '/':
return 4;
case '(':
return 0;
}
return 0;
}
// function to return precedence value
// if operator is present outside stack.
function outPrec(input)
{
switch (input) {
case '+':
case '-':
return 1;
case '*':
case '%':
case '/':
return 3;
case '(':
return 100;
}
return 0;
}
// function to convert infix to postfix
function inToPost(input)
{
let s = [];
// while input is not NULL iterate
let i = 0;
while (input.length != i) {
// if character an operand
if (isOperand(input[i]) == 1) {
document.write(input[i]);
}
// if input is an operator, push
else if (isOperator(input[i]) == 1) {
if (s.length == 0
|| outPrec(input[i]) > inPrec(s[s.length - 1])) {
s.push(input[i]);
}
else {
while (s.length != 0
&& outPrec(input[i]) < inPrec(s[s.length - 1])) {
document.write(s[s.length - 1]);
s.pop();
}
s.push(input[i]);
}
} // condition for opening bracket
else if (input[i] == ')') {
while (s[s.length - 1] != '(') {
document.write(s[s.length - 1]);
s.pop();
// if opening bracket not present
if (s.length == 0) {
document.write("Wrong input" + "</br>");
return;
}
}
// pop the opening bracket.
s.pop();
}
i++;
}
// pop the remaining operators
while (s.length != 0) {
if (s[s.length - 1] == '(') {
document.write("</br>" + " Wrong input" + "</br>");
return;
}
document.write(s[s.length - 1]);
s.pop();
}
}
let input = "a+b*c-(d/e+f*g*h)".split('');
inToPost(input);
// This code is contributed by rameshtravel07.
</script>
Producción:
abc*+de/fg*h*+-
¿Cómo manejar operadores con asociatividad de derecha a izquierda?
Por ejemplo, operador de potencia ^. El sufijo de «a^b^c» sería «abc^^», pero la solución anterior imprimiría el sufijo como «ab^c^», lo cual es incorrecto.
En la implementación anterior, cuando vemos un operador con la misma precedencia, lo tratamos como inferior. Necesitamos considerar lo mismo si los dos operadores se han ido a la asociatividad. Pero en el caso de asociatividad de derecha a izquierda, debemos tratarlo como una precedencia más alta y empujarlo a la pila.
Acercarse:
- Si el carácter de entrada es un operando, imprímalo.
- Si el carácter de entrada es un operador-
- Si la pila está vacía, empújela hacia la pila.
- Si ((su valor de precedencia es mayor que el valor de precedencia del carácter en la parte superior) O (la precedencia es la misma Y la asociatividad es de derecha a izquierda)), empuje.
- Si ((su valor de precedencia es menor) O (la precedencia es la misma Y la asociatividad es de izquierda a derecha)), entonces salta de la pila e imprime mientras la precedencia del carácter superior es mayor que el valor de precedencia del carácter de entrada.
- Si el carácter de entrada es ‘)’, extraiga e imprima hasta que la parte superior sea ‘(‘. (Extraiga ‘(‘ pero no lo imprima.)
- Si la pila se vacía antes de encontrar ‘(‘, entonces es una expresión no válida.
- Repita los pasos 1 a 4 hasta que la expresión de entrada se haya leído por completo.
- Extraiga los elementos restantes de la pila e imprímalos.