Introdução
Pilhas são um tipo de coleção muito usado na ciência da computação.
Elas são definidas por suas duas operações principais: push e pop.
Push adiciona um elemento ao topo da pilha.
Pop remove e retorna o elemento do topo.
Pense em uma pilha como uma pilha de pratos.
Você pode colocar um prato no topo da pilha ou pegar o prato que está no topo.
Para acessar algo mais abaixo, você precisa remover todos os pratos que estão por cima.
A implementação de vetor do Rust, std::vec::Vec, pode ser usada como uma pilha por meio de seus métodos push() e pop().
Naturalmente, push() adiciona um elemento ao final do Vec e pop() remove e retorna o último elemento.
Essas operações podem ser muito rápidas (O(1) na notação Big O),
então elas são uma das formas mais idiomáticas de usar um Vec.
Pilhas são úteis para guardar quantidades arbitrárias de elementos em uma ordem específica.
Como o último elemento inserido é o primeiro a ser retornado,
as pilhas costumam ser chamadas de LIFO (Last-In, First-Out), ou seja, o último a entrar é o primeiro a sair.
Essa ordenação inerente pode ser usada para muitas coisas,
inclusive para acompanhar o estado ao avaliar a notação polonesa inversa.
Instruções
1. Visão geral
A notação polonesa inversa (RPN) é uma forma de escrever expressões matemáticas.
Ao contrário da notação infixa tradicional, os operadores da RPN vêm depois dos seus operandos.
Por exemplo, em vez de escrever:
2 + 2
você escreveria:
2 2 +
A grande vantagem da notação polonesa inversa é que ela é muito mais simples de analisar do que a notação infixa.
A RPN elimina a necessidade de seguir a ordem das operações ou de usar parênteses em expressões complexas.
Por exemplo:
(4 + 8) / (7 - 5)
pode ser escrita como
4 8 + 7 5 - /
Nos dois casos, a expressão resulta em 6.
2. Exemplo
Vamos avaliar essa expressão complexa manualmente.
Como vimos na introdução, a avaliação da RPN exige uma pilha.
Essa pilha é usada para guardar os valores numéricos sobre os quais os operadores atuam.
Começamos nossa calculadora com uma pilha vazia e depois avaliamos cada elemento, um de cada vez.
Primeiro, encontramos um 4,
então o empilhamos na nossa pilha recém-criada.
4
Em seguida, encontramos um 8.
Também o empilhamos na pilha.
4 8
Agora, encontramos um +.
Desempilhamos os dois valores do topo (4 e 8),
somamos os dois
e empilhamos a soma de volta na pilha.
12
Fazemos algo parecido com 7, 5 e -:
12 7
12 7 5
12 2
Agora encontramos uma /.
Embora o último operador que encontramos tenha sido um -,
há dois elementos na pilha.
Desempilhamos os dois elementos,
dividimos um pelo outro
e empilhamos o resultado de volta na pilha.
6
Por fim, como há exatamente um elemento na pilha,
podemos dizer que a expressão resultou em 6.
3. Objetivo
Seu objetivo é escrever uma calculadora que avalie uma lista de entradas ordenadas em notação polonesa inversa e retorne o último elemento da pilha.
Se não houver exatamente um elemento na pilha no final, retorne None.
Se houver um operador com operandos insuficientes (como a entrada 2 +), retorne None.
Você recebe o enum e a função stub a seguir 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
