Inhalt
Die Fakten:
| Plattform: | codewars.com |
| Name: | Reverse polish notation calculator |
| Level: | 6 kyu |
| Sprache: | TypeScript |
Beschreibung:
Your job is to create a calculator which evaluates expressions in Reverse Polish notation.
For example expression 5 1 2 + 4 * + 3 - (which is equivalent to 5 + ((1 + 2) * 4) - 3 in normal notation) should evaluate to 14.
For your convenience, the input is formatted such that a space is provided between every token.
Empty expression should evaluate to 0.
Valid operations are +, -, *, /.
You may assume that there won't be exceptional situations (like stack underflow or division by zero).
Quelle: codewars.com
Lösung
Pseudo-Code
Wie immer gibt's reichlich Varianten, hier ist eine meiner.
Erst die Lösungsschritte in Pseudo-Code. Los geht’s:
Lösungsschritte
Schritt 1
Als Erstes wandeln wir den Input-String in ein Array um und loopen.
Schritt 2
Wir brauchen einen inneren und einen äußeren Loop.
Schritt 3
Außen loopen wir solange, wie unser Array mehr als 1 Element hat.
Schritt 4
Innen loopen wir durch jedes Element und suchen das nächste Element das keine Zahl ist.
Schritt 5
Wenn das aktuelle Element keine Zahl ist,
Schritt 6
schnappen wir uns das aktuelle und die beiden Elemente davor
Schritt 7
und basteln uns daraus unsere mathematische Operation.
Schritt 8
Dann stecken wir das Ergebnis der Operation wieder zurück ins Array.
Schritt 9
Und loopen nochmal durch das verbleibende Array (wir fahren fort mit dem äußeren Loop).
Schritt 10
Wenn nur noch 1 Element im Array ist, geben wir das zurück.
Code
Geil. Übersetzen wir unseren Pseudo-Code in TypeScript:
Lösungsschritte
Meine erste Zeile:
export function calc(expr: string): number {
Input-String in ein Array umwandeln:
const arr = expr.split(" ");
Jetzt der äußere Loop (solange wie das Array mehr als 1 Element hat):
while (arr.length > 1) {
Dann der innere Loop durch jedes Element (das noch im Array ist):
for (let i = 0; i < arr.length; i++) {
Wir prüfen, ob das aktuelle Element eine Zahl ist:
if (!Number(arr[i])) {
Wenn es keine Zahl ist, extrahieren wir das aktuelle Element und die beiden Elemente davor:
const [first, second, operator] = arr.splice(i - 2, 3);
Hier dekonstruiere ich die 3 Elemente direkt. So haben sie gleich Namen.
Dann führen wir die aktuelle Rechenoperation aus und speichern das Ergebnis:
const currResult = eval(`${first} ${operator} ${second}`);
Ich verwende hier eval(). eval() sollte man unbedingt mit Vorsicht genießen. Vor allem, wenn man mit Nutzereingaben arbeitet.
Dann fügen wir das Ergebnis wieder in unser Array ein:
arr.splice(i - 2, 0, currResult);
Das geht z.B. mit .splice(). Wenn man ein drittes Argument angibt, wird dieses am Index des erstes Argumentes eingefügt.
Dann können wir den aktuellen Schleifendurchlauf abbrechen und wieder zur while-Schleife hochspringen:
break;
}
}
}
Nach beiden Loops - wenn wir nur noch 1 Element in unserem Array haben (unser Ergebnis) - geben wir dieses als Zahl zurück:
return Number(arr[0]);
}
Voilá! 💪
Komplettlösung
export function calc(expr: string): number {
const arr = expr.split(" ");
while (arr.length > 1) {
for (let i = 0; i < arr.length; i++) {
if (!Number(arr[i])) {
const [first, second, operator] = arr.splice(i - 2, 3);
const currResult = eval(`${first} ${operator} ${second}`);
arr.splice(i - 2, 0, currResult);
break;
}
}
}
return Number(arr[0]);
}