Introduzione
Gli stack sono un tipo di collezione comunemente usata in informatica.
Sono definiti dalle loro due operazioni chiave: push e pop.
Push aggiunge un elemento in cima allo stack.
Pop rimuove e restituisce l'elemento in cima.
Immagina uno stack come una pila di piatti.
Puoi aggiungere un piatto in cima allo stack oppure prendere il piatto più in alto.
Per accedere a qualcosa più in basso, devi rimuovere tutti i piatti che stanno sopra.
Il vettore di Rust, std::vec::Vec, può essere usato come stack utilizzando i suoi metodi push() e pop().
Naturalmente, push() aggiunge un elemento alla fine del Vec e pop() rimuove e restituisce l'ultimo elemento.
Queste operazioni possono essere molto veloci (O(1) nella notazione Big O),
quindi rappresentano uno dei modi più idiomatici per usare un Vec.
Gli stack sono utili per contenere un numero arbitrario di elementi in un ordine specifico.
Poiché l'ultimo elemento inserito è il primo elemento restituito,
gli stack vengono comunemente chiamati LIFO (ultimo entrato, primo uscito).
Questo ordinamento intrinseco può essere usato per molte cose,
incluso tenere traccia dello stato quando si valuta la notazione polacca inversa.
Istruzioni
1. Panoramica
La notazione polacca inversa (RPN) è un modo di scrivere le espressioni matematiche.
A differenza della tradizionale notazione infissa, in RPN gli operatori seguono i loro operandi.
Per esempio, invece di scrivere:
2 + 2
scriveresti:
2 2 +
Il vantaggio principale della notazione polacca inversa è che è molto più semplice da analizzare rispetto alla notazione infissa.
La RPN elimina la necessità dell'ordine delle operazioni o delle parentesi nelle espressioni complesse.
Per esempio:
(4 + 8) / (7 - 5)
si può scrivere come
4 8 + 7 5 - /
In entrambi i casi, l'espressione vale 6.
2. Esempio
Valutiamo manualmente quell'espressione complessa.
Come abbiamo imparato nell'introduzione, la valutazione della RPN richiede uno stack.
Questo stack serve a contenere i valori numerici su cui operano gli operatori.
Iniziamo la calcolatrice con uno stack vuoto e poi valutiamo un elemento alla volta.
Per prima cosa incontriamo un 4, quindi lo impiliamo nello stack appena creato.
4
Poi incontriamo un 8.
Anche quello lo impiliamo nello stack.
4 8
Ora incontriamo un +.
Estraiamo i due valori più in alto (4 e 8),
li sommiamo
e impiliamo di nuovo la somma nello stack.
12
Facciamo qualcosa di simile per 7, 5 e -:
12 7
12 7 5
12 2
Ora incontriamo un /.
Anche se l'ultimo elemento incontrato era un -,
ci sono due elementi sullo stack.
Estraiamo i due elementi,
li dividiamo
e impiliamo il risultato di nuovo nello stack.
6
Infine, dato che sullo stack c'è esattamente un elemento,
possiamo dire che l'espressione vale 6.
3. Obiettivo
Il tuo obiettivo è scrivere una calcolatrice che valuti un array di input ordinati secondo la notazione polacca inversa e restituisca l'elemento finale sullo stack.
Se alla fine nello stack non c'è esattamente un elemento, restituisci None.
Se c'è un operatore con troppi pochi operandi (come l'input 2 +), restituisci None.
Come punto di partenza, ti vengono forniti il seguente enum e la funzione stub.
#[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"
);
}
Esercizio di apprendimento
