Εισαγωγή
Στοίβες είναι ένας τύπος συλλογής που χρησιμοποιείται συνήθως στην επιστήμη υπολογιστών.
Ορίζονται από τις δύο βασικές λειτουργίες τους: push και pop.
Η push προσθέτει ένα στοιχείο στην κορυφή της στοίβας.
Η pop αφαιρεί και επιστρέφει το στοιχείο στην κορυφή.
Σκέψου μια στοίβα σαν στοίβα από πιάτα.
Μπορείς είτε να προσθέσεις ένα πιάτο στην κορυφή της στοίβας είτε να πάρεις το πάνω πιάτο.
Για να προσπελάσεις κάτι πιο κάτω, πρέπει να αφαιρέσεις όλα τα πιάτα από πάνω του.
Η υλοποίηση διανύσματος της Rust, std::vec::Vec, μπορεί να χρησιμοποιηθεί ως στοίβα χρησιμοποιώντας τις μεθόδους push() και pop() της.
Φυσικά, η push() προσθέτει ένα στοιχείο στο τέλος του Vec και η pop() αφαιρεί και επιστρέφει το τελευταίο στοιχείο.
Αυτές οι λειτουργίες μπορούν να είναι πολύ γρήγορες (O(1) στον συμβολισμό Big O),
οπότε είναι ένας από τους πιο ιδιωματικούς τρόπους χρήσης ενός Vec.
Οι στοίβες είναι χρήσιμες για να κρατούν αυθαίρετους αριθμούς στοιχείων σε συγκεκριμένη σειρά.
Επειδή το τελευταίο στοιχείο που εισάγεται είναι το πρώτο στοιχείο που επιστρέφεται,
οι στοίβες συνήθως αναφέρονται ως LIFO (Τελευταίο Μέσα, Πρώτο Έξω).
Αυτή η εγγενής διάταξη μπορεί να χρησιμοποιηθεί για πολλά πράγματα,
συμπεριλαμβανομένης της παρακολούθησης κατάστασης κατά την αξιολόγηση της Αντίστροφης πολωνικής σημειογραφίας.
Οδηγίες
1. Επισκόπηση
Το Reverse Polish notation (RPN) είναι ένας τρόπος να γράφεις μαθηματικές παραστάσεις.
Σε αντίθεση με τον παραδοσιακό ενθηματικό συμβολισμό, οι τελεστές του RPN ακολουθούν τους τελεστέους τους.
Για παράδειγμα, αντί να γράψεις:
2 + 2
θα έγραφες:
2 2 +
Το μεγαλύτερο πλεονέκτημα του Reverse Polish notation είναι ότι είναι πολύ πιο απλό στην ανάλυση από τον ενθηματικό συμβολισμό.
Ο RPN εξαλείφει την ανάγκη για σειρά πράξεων ή παρενθέσεις σε περίπλοκες παραστάσεις.
Για παράδειγμα:
(4 + 8) / (7 - 5)
μπορεί να γραφτεί ως
4 8 + 7 5 - /
Και στις δύο περιπτώσεις, η παράσταση υπολογίζεται σε 6.
2. Παράδειγμα
Ας υπολογίσουμε με το χέρι αυτή την περίπλοκη παράσταση.
Όπως μάθαμε στην εισαγωγή, η αξιολόγηση μιας παράστασης RPN απαιτεί μια στοίβα.
Αυτή η στοίβα χρησιμοποιείται για να κρατά τις αριθμητικές τιμές πάνω στις οποίες δρουν οι τελεστές.
Ξεκινάμε την αριθμομηχανή μας με μια άδεια στοίβα και μετά αξιολογούμε κάθε στοιχείο ένα τη φορά.
Πρώτα, συναντάμε το 4,
οπότε το ωθούμε στη στοίβα που μόλις δημιουργήσαμε.
4
Έπειτα, συναντάμε το 8.
Το ωθούμε κι αυτό στη στοίβα.
4 8
Τώρα, συναντάμε το +.
Βγάζουμε τις δύο πάνω τιμές (4 και 8),
τις προσθέτουμε
και ωθούμε το άθροισμα πίσω στη στοίβα.
12
Κάνουμε κάτι παρόμοιο για τα 7, 5 και -:
12 7
12 7 5
12 2
Τώρα συναντάμε το /.
Αν και τελευταία συναντήσαμε το -,
υπάρχουν δύο στοιχεία στη στοίβα.
Βγάζουμε τα δύο στοιχεία,
τα διαιρούμε
και ωθούμε το αποτέλεσμα πίσω στη στοίβα.
6
Τέλος, αφού υπάρχει ακριβώς ένα στοιχείο στη στοίβα,
μπορούμε να πούμε ότι η παράσταση υπολογίστηκε σε 6.
3. Στόχος
Ο στόχος σου είναι να γράψεις μια αριθμομηχανή που να αξιολογεί μια λίστα εισόδων διατεταγμένων κατά Reverse Polish notation και να επιστρέφει το τελευταίο στοιχείο της στοίβας.
Αν στο τέλος δεν υπάρχει ακριβώς ένα στοιχείο στη στοίβα, επέστρεψε None.
Αν υπάρχει τελεστής με πολύ λίγους τελεστέους (όπως η είσοδος 2 +), επέστρεψε None.
Σου δίνονται το παρακάτω enum και μια σκελετωμένη συνάρτηση ως σημείο εκκίνησης.
#[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"
);
}
Άσκηση εκμάθησης
