Introducción
Las pilas son un tipo de colección que se usa mucho en informática.
Se definen por sus dos operaciones clave: push y pop.
Push añade un elemento a lo alto de la pila.
Pop elimina y devuelve el elemento que está más arriba.
Piensa en una pila como en un montón de platos.
Puedes añadir un plato encima del montón o coger el plato que está más arriba.
Para acceder a algo que está más abajo, tienes que quitar antes todos los platos que hay encima.
La implementación de vectores de Rust, std::vec::Vec, se puede usar como una pila usando sus métodos push() y pop().
Como es natural, push() añade un elemento al final del Vec y pop() elimina y devuelve el último elemento.
Estas operaciones pueden ser muy rápidas (O(1) en notación O grande),
así que son una de las formas más idiomáticas de usar un Vec.
Las pilas son útiles para guardar un número arbitrario de elementos en un orden concreto.
Como el último elemento que se inserta es el primero que se devuelve,
a las pilas se las suele llamar LIFO (del inglés Last-In, First-Out: «el último en entrar es el primero en salir»).
Este orden inherente se puede usar para muchas cosas,
como llevar la cuenta 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, los operadores de la RPN van después de sus operandos.
Por ejemplo, en lugar de escribir:
2 + 2
escribirías:
2 2 +
La principal ventaja de la notación polaca inversa es que es mucho más fácil de analizar que la notación infija.
La RPN elimina la necesidad del orden de las operaciones o de los 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 se evalúa como 6.
2. Ejemplo
Vamos a evaluar manualmente esa expresión compleja.
Como vimos en la introducción, para evaluar una RPN hace falta una pila.
Esta pila se usa para almacenar los valores numéricos sobre los que operan los operadores.
Empezamos con una pila vacía en nuestra calculadora y luego evaluamos cada elemento de uno en uno.
Primero, nos encontramos con un 4,
así que lo metemos en la pila que acabamos de crear.
4
Después, nos encontramos con un 8.
También lo metemos en la pila.
4 8
Ahora, nos encontramos con un +.
Sacamos los dos valores de arriba (4 y 8),
los sumamos
y volvemos a meter la suma 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 los dos elementos,
los dividimos
y volvemos a meter el resultado en la pila.
6
Por último, como hay exactamente un elemento en la pila,
podemos decir que la expresión se evalúa como 6.
3. Objetivo
Tu objetivo es escribir una calculadora que evalúe una lista de entradas ordenadas según la notación polaca inversa y devuelva el último elemento 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 la entrada 2 +), devuelve None.
Como punto de partida, te damos la siguiente enumeración y una función sin implementar.
#[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
