Introducción
Las pilas son un tipo de colección que se usa mucho en ciencias de la computación.
Se definen por sus dos operaciones clave: push y pop.
Push agrega un elemento al tope de la pila.
Pop quita y devuelve el elemento del tope.
Piensa en una pila como en una pila de platos.
Puedes agregar un plato al tope de la pila o tomar el plato de arriba.
Para llegar a algo que está más abajo, tienes que quitar todos los platos que están encima.
La implementación de vectores de Rust, std::vec::Vec, se puede usar como una pila usando sus métodos push() y pop().
Naturalmente, push() agrega un elemento al final del Vec y pop() quita y devuelve el último elemento.
Estas operaciones pueden ser muy rápidas (O(1) en notación Big O),
así que son una de las formas más idiomáticas de usar un Vec.
Las pilas son útiles para guardar cantidades arbitrarias de elementos en un orden específico.
Como el último elemento que se inserta es el primero que se devuelve,
a las pilas se las conoce comúnmente como LIFO (último en entrar, primero en salir).
Este orden inherente se puede usar para muchas cosas,
como llevar el seguimiento del estado al evaluar la notación polaca inversa.
Instrucciones
1. Descripción general
La notación polaca inversa (RPN) es una forma de escribir expresiones matemáticas.
A diferencia de la notación infija tradicional, en la RPN los operadores van después de sus operandos.
Por ejemplo, en vez de escribir:
2 + 2
escribirías:
2 2 +
La gran ventaja de la notación polaca inversa es que resulta mucho más sencilla de interpretar que la notación infija.
La RPN elimina la necesidad de respetar un orden de operaciones o de usar paréntesis en expresiones complejas.
Por ejemplo:
(4 + 8) / (7 - 5)
se puede escribir como
4 8 + 7 5 - /
En ambos casos, la expresión da como resultado 6.
2. Ejemplo
Evaluemos manualmente esa expresión compleja.
Como vimos en la introducción, para evaluar una expresión en RPN se necesita una pila.
Esta pila sirve para guardar los valores numéricos sobre los que operan los operadores.
Empezamos nuestra calculadora con una pila vacía y luego evaluamos cada elemento, uno a la vez.
Primero nos encontramos con un 4,
así que lo apilamos en la pila que acabamos de crear.
4
Luego nos encontramos con un 8.
También lo apilamos en la pila.
4 8
Ahora nos encontramos con un +.
Sacamos los dos valores de arriba (4 y 8),
los sumamos
y apilamos el resultado de vuelta en la pila.
12
Hacemos algo parecido con 7, 5 y -:
12 7
12 7 5
12 2
Ahora nos encontramos con un /.
Aunque lo último que encontramos fue un -,
hay dos elementos en la pila.
Sacamos esos dos elementos,
los dividimos
y apilamos el resultado de vuelta en la pila.
6
Por último, como queda exactamente un elemento en la pila,
podemos decir que la expresión dio como resultado 6.
3. Objetivo
Tu objetivo es escribir una calculadora que evalúe una lista de argumentos ordenados según la notación polaca inversa y que devuelva el elemento final de la pila.
Si al final no hay exactamente un elemento en la pila, devuelve None.
Si hay un operador con muy pocos operandos (como el argumento 2 +), devuelve None.
Te damos el siguiente enum y la siguiente función sin implementar como punto de partida.
#[derive(Debug)]
pub enum CalculatorInput {
Add,
Subtract,
Multiply,
Divide,
Value(i32),
}
pub fn evaluate(inputs: &[CalculatorInput]) -> Option<i32> {
todo!(
"Given the inputs: {inputs:?}, evaluate them as though they were a Reverse Polish notation expression"
);
}
Ejercicio de aprendizaje
