Comprender el orden de las operaciones en programación

Introducción

Como programador, probablemente esté acostumbrado a decirle a las computadoras qué hacer. Escriba un código, ejecútelo y la computadora se pondrá a trabajar ejecutando cualquier comando que le haya dado.

Aunque tenemos este poderoso reinado sobre las computadoras, todavía hay mucha magia que ocurre constantemente en nuestro código y que solemos pasar por alto. Esto es especialmente cierto si trabajas con lenguajes de alto nivel con funciones predefinidas, como la mayoría de nosotros. Y, por supuesto, si bien no hay una razón real para reinventar la rueda o tratar de implementar estas útiles funciones por tu cuenta, ¡sigue siendo divertido echar un vistazo bajo el capó y ver qué está pasando!

En este artículo analizaremos en profundidad uno de esos conceptos que probablemente todos hemos utilizado en algún momento: el orden de las operaciones.

Digamos que desea evaluar esta expresión de muestra:

5 + 10 * 3

10 by 3Según el orden matemático de las operaciones, primero multiplicarías y luego sumarías 5al producto de eso, pero ¿cómo exactamente le dirías a una computadora que haga esto?

Hay diferentes maneras de analizar esta ecuación, pero algunas requieren un poco más de conocimientos que otras.

Este tutorial convertirá la ecuación al formato correcto. Una vez que esté en un formato más legible por máquina, podrá pasarla por el algoritmo de análisis que la calculará. Este tutorial se centrará en cuatro operadores: suma, resta, multiplicación y división.

Entendiendo la diferencia entre infijo y sufijo

Aunque quizás no te hayas dado cuenta todavía, probablemente ya estés familiarizado con la notación infija. La expresión de ejemplo está escrita en notación infija:

5 + 10 * 3

Significa que los operadores se encuentran entre los operandos sobre los que actúan.

¿Qué es la notación postfija?

Como se mencionó anteriormente, es necesario convertir la ecuación a un formato que la computadora pueda entender. Este formato se denomina notación posfija.

Las expresiones escritas en notación postfija tendrán todos los operadores después de sus operandos.

Esto es importante porque cuando la máquina lee expresiones en este formato, nunca encontrará un operador antes de los operandos sobre los que está actuando, lo que significa que no tendrá que ir y venir.

Así que la expresión de ejemplo:

5 + 10 * 3

Se convierte en:

5 10 3 * +

Puede que parezca extraño, pero existe una metodología para llegar a esto.

Una forma sencilla de convertir de infijo a sufijo

Añadir entre paréntesis en orden de precedencia:

    (5 + (10 * 3))

Mueva cada operador a la derecha, directamente antes de su paréntesis de cierre:

    (5 (10 3 *) +)

Ahora elimine los paréntesis por completo, lo que le deja la expresión en notación sufija:

    5 10 3 * +

He aquí otro ejemplo para demostrar que los operadores no necesariamente estarán siempre al final:

8 * 4 + 2((8 * 4) + 2)((8 4 *) 2 +)8 4 * 2 +

Nuevamente, esto no es lo ideal para que lo haga la computadora, ya que no sabría dónde poner los paréntesis. Afortunadamente, existe un algoritmo que produce los mismos resultados.

Aplicación del algoritmo del patio de maniobras

El algoritmo del patio de maniobras fue desarrollado por Dijkstra como un medio para convertir la notación infija en notación posfija.

Antes de continuar, revisemos rápidamente las dos estructuras de datos que usará aquí: una pila y una cola. Puede usar una matriz para almacenar ambos conjuntos de datos. La principal diferencia surge del orden en que agrega y elimina los datos.

Cola : cuando agregas datos a una cola, los estás empujando hacia el final. Solo imagina que estás haciendo fila para un evento y cada persona en la fila es un elemento en la cola. Cuando te acercas a la fila, automáticamente te insertan al final de la fila. A medida que el evento comienza a admitir personas (eliminando elementos de la cola), retiran a las personas del frente de la fila ya que esas personas han estado allí por más tiempo. Puedes recordar esto con el acrónimo FIFO: primero en entrar, primero en salir.

Pila : cada vez que agregas un nuevo elemento a la pila, se colocará en la parte superior (o al frente) en lugar de en la parte posterior. Cuando quieras eliminar un elemento de la pila, quitarás el elemento superior. Debido a que los elementos nuevos siempre van en la parte superior, esos nuevos elementos siempre se quitarán primero cuando necesites eliminar algo. Esto se puede recordar con el acrónimo LIFO: último en entrar, primero en salir.

Nota: En el resto de este tutorial se utilizarán los términos push y pop para las pilas. Una acción push se refiere a agregar un nuevo elemento a la parte superior de la pila. Una acción pop se refiere a eliminar el elemento agregado más recientemente de la parte superior de la pila.

Para este algoritmo, supongamos que tiene una pila temporal para almacenar los operadores (pila de operadores) y una cola que contendrá el resultado final.

Cómo funciona

El algoritmo del patio de maniobras sigue cuatro pasos básicos:

1. Analice la expresión de izquierda a derecha.
2. Si ve un operando, envíelo inmediatamente a la cola de resultados.
3. Si ve un operador:
   • Si la pila del operador está vacía, empuje al operador entrante hacia la pila del operador.
   • Si el operador entrante tiene mayor precedencia que el que se encuentra actualmente en la parte superior de la pila de operadores, empuje el operador entrante a la parte superior de la pila.
   • Si el operador entrante tiene igual precedencia, extraiga el operador superior de la pila, envíelo a la cola y coloque el operador entrante en la pila.
   • Si el operador entrante tiene menor precedencia, extraiga el operador superior de la pila, envíelo a la cola y pruebe el operador entrante con la nueva parte superior de la pila.
4. Una vez que haya analizado toda la expresión, extraiga todos los tokens restantes de la pila de operadores.

Evaluación de una expresión infija con el algoritmo del patio de maniobras

Es difícil entender esos pasos sin verlos en acción, así que repasemos el ejemplo anterior e intentemos formatearlo con el algoritmo.

Convierte esta ecuación de notación infija a notación posfija:

5 + 10 * 3

Configuremos sus dos matrices: una para la salida de resultados y otra para la pila de operadores temporales:

    expression = 5 + 10 * 3    output = []    operator stack = []

Primero, comienza a leer la expresión de izquierda a derecha. Primero tienes 5. Como se trata de un operando, puedes mostrarlo inmediatamente:

    expression = + 10 * 3    output = [5]    operator stack = []

A continuación, verás que +la pila de operadores está vacía, por lo que puedes insertarla allí:

    expression = 10 * 3    output = [5]    operator stack = [+]

El siguiente es 10, por lo que su salida será inmediata:

    expression = * 3    output = [5, 10]    operator stack = [+]

Ahora, se utiliza otro operador, *. Como la pila de operadores no está vacía, hay que compararla con la parte superior actual de la pila de operadores para ver cuál tiene mayor precedencia.

El valor actual que se encuentra en la parte superior de la pila es +. Por lo tanto, al comparar los dos, se sabe que la multiplicación tiene mayor precedencia que la suma.

Esto significa que puedes empujarlo hacia la parte superior de la pila, lo que te brinda:

    expression = 3    output = [5, 10]    operator stack = [*, +]

Ahora has llegado al valor final, 3. Como no se trata de un operador, puedes mostrarlo inmediatamente:

    expression is now empty    output = [5, 10, 3]    operator stack = [*, +]

Dado que la expresión ahora está vacía, todo lo que queda es extraer todos los tokens de la pila de operadores y generarlos de inmediato. Cuando extraes de la pila, tomas desde arriba, por lo que primero tomarás el *para empujarlo hasta el final de la cola y luego tomarás el +.

    output = [5, 10, 3, *, +]

¡Y eso es todo! Como puedes ver, es igual que el método anterior, donde se agregan paréntesis, pero de esta manera es mucho más fácil de hacer para una computadora.

Reglas de precedencia

Quizás hayas notado que hubo un punto en el que, en lugar de usar el algoritmo para decidir, confiaste en tu propio conocimiento para elegir qué hacer a continuación: determinar qué operador tenía mayor precedencia.

No es importante ahora mientras comprendes los conceptos detrás del algoritmo, pero cuando escribas el código real para resolver esto, tendrás que incorporar algunas reglas de precedencia.

Tienes que crear un objeto que básicamente clasifique cada operador. A los operadores de multiplicación y división les darás un rango de 2 y a los operadores de suma y resta un rango de 1.

Cuando lo codifiques, compararás dos operadores comparando su rango numérico. Los números reales 1 y 2 aquí son arbitrarios, así que no te obsesiones demasiado con eso. Comprende el concepto de que la multiplicación tiene un rango superior a la suma, por lo que tiene un número más alto.

    const precedence = {        "*": 2,        "/": 2,        "+": 1,        "-": 1    };

Evaluación de una expresión de sufijo

Finalmente tienes la expresión en notación sufija. Ahora puedes usar este formato para evaluarla.

Algoritmo para evaluar la expresión

Aquí te explicamos cómo hacerlo:

1. Comience con una pila vacía.
2. Analizar el primer token en la expresión.
3. Si es un operando, empújelo hacia la pila.
4. Si se trata de un operador, extrae la cantidad adecuada de operandos de la pila y colócalos en variables temporales. (Por ejemplo, la multiplicación es un operador binario, por lo que si estás analizando y encuentras un operador de multiplicación, entonces sabrás que debes extraer dos operandos).
5. Evalúe esa expresión utilizando el operador actual y los dos operandos que se extrajeron.
6. Empuja ese resultado a la parte superior de la pila.
7. Repita los pasos 2 a 7 hasta que la expresión esté vacía.

En el ejemplo, solo se trabaja con operadores binarios, por lo que siempre se pueden eliminar dos operandos cuando se ve un operador. Si se desea ampliar el ejemplo para que pueda manejar todos los operadores, se deben manejar operadores unarios como !.

Recorriendo el algoritmo

Recorramos un pseudocódigo donde usamos el algoritmo para evaluar la expresión de notación sufija de muestra:

5 10 3 * +

Primero, comienza empujando cada operando en la pila hasta que llegues a un operador:

    expression = [5, 10, 3, *, +]    - push 5    - push 10    - push 3    stack = [3, 10, 5]

Ahora llegas al primer operador, *, lo que significa que es hora de empezar a extraer valores. Extraes hasta que tengas dos valores:

    - pop 3    - pop 10

Bien, ahora tienes tus dos operandos, 3y 10, así que combinarás esto con tu operador, *, dejándote con 10 * 3:

    expression = [+]    stack = [5]    tempOperand1 = 3    tempOperand2 = 10tempOperator = *eval(tempOperand1 + tempOperator + tempOperand2) // 3 * 10

Lo evalúas, obtienes 30y luego lo vuelves a colocar en la pila. Ahora tienes lo siguiente:

    expression = [+]    stack = [30, 5]

Entonces, comienzas a analizar la expresión nuevamente y de inmediato te encuentras con un operador. Nuevamente, tienes que extraer de la pila hasta que tengas dos operandos:

    expression = []    stack = []    tempOperand1 = 30    tempOperand2 = 5    tempOperator = + eval(tempOperand1 + tempOperator + tempOperand2) // 30 + 5

Haces estallar 30y 5ya estás listo para evaluar de nuevo. 5 + 30te da 35y ahora puedes volver a empujar esto a la pila.

Volviendo a tu expresión original para analizar el siguiente token, ¡descubres que está vacío!

    expression = []    stack = [35]

Esto significa que ya terminaste o que la expresión original estaba mal formada.

Comprobémoslo observando tu pila. Solo tiene un valor, por lo que esto significa que has terminado y 35es el resultado final de la expresión original 5 + 10 * 3.

Comprensión de la notación de prefijos

El algoritmo para evaluar una expresión en notación de prefijo es básicamente el mismo, excepto que esta vez se leerá de derecha a izquierda. Una pequeña modificación en el código y también podemos evaluar la notación de prefijo.

Si vuelves a tu método original de agregar paréntesis y mover operadores, puedes convertir a notación de prefijo de la misma manera que hiciste con la notación posfija. En lugar de mover los operadores al final de sus operandos, los moverás al principio. Una vez que hayas hecho eso, puedes eliminar los paréntesis por completo y entonces tendrás tu expresión de notación de prefijo.

    5 + 10 * 3    (5 + (10 * 3))    (+ 5 (* 10 3))    + 5 * 10 3

Si quieres poner a prueba tus conocimientos, intenta descubrir cómo harías esto algorítmicamente con una pequeña modificación al algoritmo del patio de maniobras.

Conclusión

En este tutorial, ha creado un algoritmo para convertir expresiones a notación posfija y lo ha probado evaluando una expresión.