Introdução
Pilhas são um tipo de coleção muito usado em informática.
Definem-se pelas suas duas operações principais: push e pop.
O push adiciona um elemento ao topo da pilha.
O pop remove e devolve o elemento que está no topo.
Pensa numa pilha como numa pilha de pratos.
Podes adicionar um prato ao topo da pilha ou tirar o prato que está no topo.
Para chegar a algo que está mais abaixo, tens de tirar todos os pratos que estão por cima.
A implementação de vetores do Rust, std::vec::Vec, pode ser usada como pilha através dos seus métodos push() e pop().
Naturalmente, push() adiciona um elemento ao fim do Vec e pop() remove e devolve o último elemento.
Estas operações podem ser muito rápidas (O(1) em Notação Big O),
por isso são uma das formas mais idiomáticas de usar um Vec.
As pilhas são úteis para guardar um número arbitrário de elementos numa ordem específica.
Como o último elemento inserido é o primeiro a ser devolvido,
as pilhas são habitualmente designadas por LIFO (Last-In, First-Out).
Esta ordem inerente pode ser usada para muitas coisas,
incluindo acompanhar o estado ao avaliar notação polaca inversa.
Instruções
1. Visão geral
A notação polaca inversa (NPI) é uma forma de escrever expressões matemáticas.
Ao contrário da notação infixa tradicional, os operadores da NPI seguem os seus operandos.
Por exemplo, em vez de escreveres:
2 + 2
escreverias:
2 2 +
A grande vantagem da notação polaca inversa é que é muito mais simples de analisar do que a notação infixa.
A NPI elimina a necessidade de ordem das operações ou de parênteses em expressões complexas.
Por exemplo:
(4 + 8) / (7 - 5)
pode ser escrita como
4 8 + 7 5 - /
Em ambos os casos, a expressão dá 6.
2. Exemplo
Vamos avaliar manualmente essa expressão complexa.
Como aprendemos na introdução, avaliar uma expressão em NPI requer uma pilha.
Esta pilha serve para guardar os valores numéricos sobre os quais os operadores atuam.
Começamos a nossa calculadora com uma pilha vazia e depois avaliamos cada elemento, um de cada vez.
Primeiro, encontramos um 4,
por isso colocamo-lo na pilha que acabámos de criar.
4
A seguir, encontramos um 8.
Também o colocamos na pilha.
4 8
Agora, encontramos um +.
Retiramos os dois valores do topo (4 e 8),
somamo-los
e voltamos a colocar a soma na pilha.
12
Fazemos algo semelhante para 7, 5 e -:
12 7
12 7 5
12 2
Agora encontramos um /.
Apesar de o último operador que encontrámos ter sido um -,
há dois elementos na pilha.
Retiramos os dois elementos,
dividimo-los
e voltamos a colocar o resultado na pilha.
6
Por fim, como há exatamente um elemento na pilha,
podemos dizer que a expressão deu 6.
3. Objetivo
O teu objetivo é escrever uma calculadora que avalie uma lista de entradas ordenadas segundo a notação polaca inversa e devolva o elemento final da pilha.
Se no final não houver exatamente um elemento na pilha, devolve None.
Se houver um operador com poucos operandos (como a entrada 2 +), devolve None.
É-te fornecido o seguinte enum e a função esboçada como ponto 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"
);
}
Exercício de aprendizagem
