Bevezetés
A vermek a számítástechnikában gyakran használt gyűjteménytípus. Két kulcsfontosságú műveletük határozza meg őket: a push és a pop. A push egy elemet tesz a verem tetejére, a pop pedig eltávolítja és visszaadja a legfelső elemet.
Gondolj a veremre úgy, mint az egymásra rakott tányérokra. Vagy teszel egy tányért a kupac tetejére, vagy elveszed a legfelső tányért. Ha egy lentebbi tányérhoz akarsz hozzáférni, el kell távolítanod az összes felette lévőt.
A Rust vektoros megvalósítása, a std::vec::Vec, veremként használható a push() és a pop() metódusával. A push() természetesen a Vec végére fűz egy elemet, a pop() pedig eltávolítja és visszaadja az utolsó elemet. Ezek a műveletek nagyon gyorsak lehetnek (O(1) a nagy ordó jelölésben), így az egyik legidiomatikusabb módját jelentik a Vec használatának.
A vermek arra hasznosak, hogy tetszőleges számú elemet tároljanak egy meghatározott sorrendben. Mivel az utoljára bekerült elem kerül vissza elsőként, a vermeket gyakran LIFO-nak (Last-In, First-Out, azaz utolsóként be, elsőként ki) nevezik. Ez a beépített sorrend sok mindenre használható, többek között az állapot követésére is, amikor fordított lengyel jelölést értékelünk ki.
Utasítások
1. Áttekintés
A fordított lengyel jelölés (RPN) a matematikai kifejezések egyik írásmódja.
A hagyományos infix jelöléssel ellentétben az RPN operátorai az operandusaik után állnak.
Például ahelyett, hogy ezt írnád:
2 + 2
helyette ezt írnád:
2 2 +
A fordított lengyel jelölés legnagyobb előnye, hogy sokkal egyszerűbb elemezni, mint az infix jelölést.
Az RPN-nél összetett kifejezésekben sincs szükség műveleti sorrendre vagy zárójelekre.
Például:
(4 + 8) / (7 - 5)
így írható fel:
4 8 + 7 5 - /
Mindkét esetben a kifejezés értéke 6.
2. Példa
Értékeljük ki kézzel ezt az összetett kifejezést.
Ahogy a bevezetőben megtanultuk, az RPN kiértékeléséhez veremre van szükség.
Ez a verem tárolja azokat a számértékeket, amelyekkel az operátorok dolgoznak.
A számológépünket egy üres veremmel indítjuk, majd egyenként kiértékeljük az elemeket.
Először egy 4-gyel találkozunk,
ezért betesszük az imént létrehozott verembe.
4
Ezután egy 8-cal találkozunk.
Ezt is betesszük a verembe.
4 8
Most a + jel következik.
Kivesszük a legfelső két értéket (4 és 8),
összeadjuk őket,
majd az összeget visszatesszük a verembe.
12
Ugyanígy járunk el a 7, 5 és - esetében is:
12 7
12 7 5
12 2
Most a / jel következik.
Bár legutóbb a - jelet láttuk,
két elem van a veremben.
Kivesszük a két elemet,
elosztjuk őket,
majd az eredményt visszatesszük a verembe.
6
Végül, mivel pontosan egy elem van a veremben,
azt mondhatjuk, hogy a kifejezés értéke 6.
3. Cél
A célod, hogy írj egy számológépet, amely kiértékeli a fordított lengyel jelöléssel megadott bemenetek listáját, és visszaadja a verem utolsó elemét.
Ha a végén nem pontosan egy elem van a veremben, adj vissza None-t.
Ha egy operátornak túl kevés operandusa van (például a 2 + bemenetnél), adj vissza None-t.
Kiindulópontként a következő enumot és csonkolt függvényt kapod.
#[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"
);
}
Tanulófeladat
