Einführung
Stacks sind eine Art Sammlung, die in der Informatik häufig verwendet wird.
Sie werden durch ihre zwei wichtigsten Operationen definiert: push und pop.
Push legt ein Element oben auf den Stack.
Pop entfernt das oberste Element und gibt es zurück.
Stell dir einen Stack wie einen Stapel Teller vor.
Du kannst entweder einen Teller oben auf den Stapel legen oder den obersten Teller nehmen.
Um an etwas weiter unten zu kommen, musst du erst alle Teller darüber entfernen.
Die Vektorimplementierung von Rust, std::vec::Vec, kannst du als Stack verwenden, indem du ihre Methoden push() und pop() benutzt.
push() fügt natürlich ein Element am Ende des Vec hinzu, und pop() entfernt das letzte Element und gibt es zurück.
Diese Operationen sind sehr schnell (O(1) in der Big-O-Notation),
deshalb sind sie eine der idiomatischsten Arten, einen Vec zu verwenden.
Stacks eignen sich gut, um eine beliebige Anzahl von Elementen in einer bestimmten Reihenfolge zu speichern.
Da das zuletzt eingefügte Element zuerst zurückgegeben wird,
werden Stacks üblicherweise als LIFO (Last-In, First-Out) bezeichnet.
Diese inhärente Reihenfolge lässt sich für vieles nutzen,
zum Beispiel um beim Auswerten der umgekehrten polnischen Notation den Zustand zu verfolgen.
Anleitung
1. Überblick
Umgekehrte Polnische Notation (UPN) ist eine Art, mathematische Ausdrücke aufzuschreiben.
Anders als in der üblichen Infixnotation folgen die Operatoren bei der UPN ihren Operanden.
Zum Beispiel schreibst du statt:
2 + 2
Folgendes:
2 2 +
Der große Vorteil der Umgekehrten Polnischen Notation ist, dass sie sich viel einfacher parsen lässt als die Infixnotation.
Die UPN macht in komplexen Ausdrücken sowohl die Rechenreihenfolge als auch Klammern überflüssig.
Zum Beispiel:
(4 + 8) / (7 - 5)
lässt sich schreiben als
4 8 + 7 5 - /
In beiden Fällen ergibt der Ausdruck den Wert 6.
2. Beispiel
Werten wir diesen komplexen Ausdruck einmal von Hand aus.
Wie wir in der Einführung gelernt haben, braucht man zur Auswertung der UPN einen Stack.
Dieser Stack enthält die numerischen Werte, auf die die Operatoren wirken.
Wir starten unseren Rechner mit einem leeren Stack und werten dann jedes Element einzeln aus.
Zuerst stoßen wir auf eine 4,
also legen wir sie auf unseren frisch erstellten Stack.
4
Als Nächstes stoßen wir auf eine 8.
Auch die legen wir auf den Stack.
4 8
Jetzt stoßen wir auf ein +.
Wir nehmen die beiden obersten Werte vom Stack (4 und 8),
addieren sie
und legen die Summe wieder auf den Stack.
12
Ähnlich machen wir es mit 7, 5 und -:
12 7
12 7 5
12 2
Jetzt stoßen wir auf ein /.
Obwohl wir zuletzt auf ein - gestoßen sind,
liegen zwei Elemente auf dem Stack.
Wir nehmen die beiden Elemente vom Stack,
dividieren sie
und legen das Ergebnis wieder auf den Stack.
6
Zum Schluss können wir, da genau ein Element auf dem Stack liegt,
sagen, dass der Ausdruck den Wert 6 ergibt.
3. Ziel
Dein Ziel ist es, einen Rechner zu schreiben, der eine Liste von Eingaben in umgekehrter polnischer Notation auswertet und das letzte Element auf dem Stack zurückgibt.
Wenn am Ende nicht genau ein Element auf dem Stack liegt, gib None zurück.
Wenn ein Operator zu wenige Operanden hat (wie bei der Eingabe 2 +), gib None zurück.
Als Ausgangspunkt bekommst du das folgende Enum und das folgende Funktionsgerüst.
#[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"
);
}
Lernübung
