Antes de comprender la conversión de notación infija a postfija, debemos conocer las notaciones infija y postfija por separado.

Un infijo y un sufijo son las expresiones. Una expresión consta de constantes, variables y símbolos. Los símbolos pueden ser operadores o paréntesis. Todos estos componentes deben organizarse de acuerdo con un conjunto de reglas para que todas estas expresiones puedan evaluarse utilizando el conjunto de reglas.

Ejemplos de expresiones son:

5 + 6

A-B

¿Qué es el altavoz?

(P*5)

Todas las expresiones anteriores tienen una estructura común, es decir, tenemos un operador entre los dos operandos. Un operando es un objeto o valor sobre el cual se va a realizar la operación. En las expresiones anteriores, 5, 6 son los operandos, mientras que '+', '-' y '*' son los operadores.

¿Qué es la notación infija?

Cuando el operador se escribe entre los operandos, entonces se conoce como notación infija . El operando no tiene por qué ser siempre una constante o una variable; también puede ser una expresión en sí misma.

Por ejemplo,

(p+q)*(r+s)

En la expresión anterior, ambas expresiones del operador de multiplicación son los operandos, es decir, (p+q) , y (r + s) son los operandos.

En la expresión anterior, hay tres operadores. Los operandos del primer operador más son p y q, los operandos del segundo operador más son r y s. Mientras realiza el operaciones en la expresión, debemos seguir un conjunto de reglas para evaluar el resultado. En el expresión anterior, la operación de suma se realizaría en las dos expresiones, es decir, p+q y r+s, y luego se realizaría la operación de multiplicación.

La sintaxis de la notación infija se proporciona a continuación:

Si solo hay un operador en la expresión, no es necesario aplicar ninguna regla. Por ejemplo, 5 + 2; en esta expresión se puede realizar la operación de suma entre los dos operandos (5 y 2), y el resultado de la operación sería 7.

Si hay varios operadores en la expresión, entonces se debe seguir alguna regla para evaluar la expresión.

Si la expresión es:

4 + 6 * 2

Si primero se evalúa el operador más, la expresión quedaría así:

10 * 2 = 20

Si primero se evalúa el operador de multiplicación, la expresión quedaría así:

4 + 12 = 16

El problema anterior se puede resolver siguiendo las reglas de precedencia de operadores. En la expresión algebraica, el orden de precedencia de los operadores se da en la siguiente tabla:

La primera preferencia se da al paréntesis; luego se da preferencia a los exponentes. En el caso de operadores de exponentes múltiples, la operación se aplicará de derecha a izquierda.

Por ejemplo:

2^2^3 = 2 ^ 8

= 256

Después de evaluar los operadores de exponente, multiplicación y división. Si ambos operadores están presentes en la expresión, la operación se aplicará de izquierda a derecha.

La siguiente preferencia se da a la suma y la resta. Si ambos operadores están disponibles en la expresión, vamos de izquierda a derecha.

Los operadores que tienen la misma precedencia se denominan asociatividad del operador . Si vamos de izquierda a derecha, entonces se le conoce como asociativo por izquierda. Si vamos de derecha a izquierda, entonces se le conoce como asociativo por la derecha.

Problema con la notación infija

Para evaluar la expresión infija, debemos conocer la precedencia del operador reglas, y si los operadores tienen la misma precedencia, entonces debemos seguir las asociatividad normas. El uso de paréntesis es muy importante en notación infija para controlar el orden en el que se realizará la operación. El paréntesis mejora la legibilidad de la expresión. Una expresión infija es la forma más común de escribir expresiones, pero no es fácil analizar y evaluar la expresión infija sin ambigüedad. Entonces, los matemáticos y lógicos estudiaron este problema y descubrieron otras dos formas de escribir expresiones: prefijo y posfijo. Ambas expresiones no requieren ningún paréntesis y pueden analizarse sin ambigüedad. No requiere reglas de precedencia de operadores ni de asociatividad.

cómo convertir una cadena a int java

Expresión sufijo

La expresión sufijo es una expresión en la que el operador se escribe después de los operandos. Por ejemplo, la expresión sufija de notación infija (2+3) se puede escribir como 23+.

Algunos puntos clave con respecto a la expresión postfix son:

• En una expresión postfija, las operaciones se realizan en el orden en que se escribieron de izquierda a derecha.
• No requiere ningún paréntesis.
• No necesitamos aplicar reglas de precedencia de operadores ni reglas de asociatividad.

Algoritmo para evaluar la expresión postfix.

• Escanee la expresión de izquierda a derecha hasta que encontremos algún operador.
• realizar la operación
• Reemplace la expresión con su valor calculado.
• Repita los pasos del 1 al 3 hasta que no existan más operadores.

Entendamos el algoritmo anterior a través de un ejemplo.

Expresión infija: 2 + 3 * 4

en una cadena java

Comenzaremos a escanear desde el extremo izquierdo de la expresión. El operador de multiplicación es un operador que aparece primero cuando se escanea de izquierda a derecha. Ahora la expresión sería:

Expresión = 2 + 34*

= 2 + 12

Nuevamente escanearemos de izquierda a derecha y la expresión sería:

Expresión = 2 12 +

= 14

Evaluación de expresión postfix usando stack.

• Escanee la expresión de izquierda a derecha.
• Si encontramos algún operando en la expresión, lo insertamos en la pila.
• Cuando encontramos cualquier operador en la expresión, sacamos los operandos correspondientes de la pila.
• Cuando terminamos con el escaneo de la expresión, el valor final permanece en la pila.

Entendamos la evaluación de la expresión postfija usando la pila.

Ejemplo 1: expresión sufijo: 2 3 4 * +

El resultado de la expresión anterior es 14.

Ejemplo 2: expresión sufijo: 3 4 * 2 5 * +

El resultado de la expresión anterior es 22.

Algoritmo para evaluar la expresión postfix.

1. leer un personaje
2. Si el carácter es un dígito, conviértalo en int y coloque el número entero en la pila.
3. Si el personaje es un operador,
   • Saque los elementos de la pila dos veces obteniendo dos operandos.
   • realizar la operación
   • Empuje el resultado a la pila.

Conversión de infijo a postfijo

Aquí, usaremos la estructura de datos de la pila para la conversión de una expresión infija en una expresión de prefijo. Siempre que encontramos un operador, lo empujamos hacia la pila. Si encontramos un operando, lo agregamos a la expresión.

Reglas para la conversión de expresión infija a postfija

1. Imprime el operando a medida que llegan.
2. Si la pila está vacía o contiene un paréntesis izquierdo en la parte superior, empuje el operador entrante hacia la pila.
3. Si el símbolo entrante es '(', empújelo a la pila.
4. Si el símbolo entrante es ')', saque la pila e imprima los operadores hasta encontrar el paréntesis izquierdo.
5. Si el símbolo entrante tiene mayor prioridad que la parte superior de la pila, empújelo sobre la pila.
6. Si el símbolo entrante tiene menor prioridad que la parte superior de la pila, extraiga e imprima la parte superior de la pila. Luego pruebe el operador entrante con la nueva parte superior de la pila.
7. Si el operador entrante tiene la misma precedencia que la parte superior de la pila, utilice las reglas de asociatividad. Si la asociatividad es de izquierda a derecha, abra e imprima la parte superior de la pila y luego presione el operador entrante. Si la asociatividad es de derecha a izquierda, presione el operador entrante.
8. Al final de la expresión, extraiga e imprima todos los operadores de la pila.

Entendamos a través de un ejemplo.

Expresión infija: K + L - M*N + (O^P) * W/U/V * T + Q

La expresión sufija final de la expresión infija (K + L - M*N + (O^P) * W/U/V * T + Q) es KL+MN*-OP^W*U/V/T*+Q+ .