Präfix berechnen

[lenaS]

Hallöchen,
ich bin recht neu in Java und soll nun eine Methode schreiben, die ein Array und einen Startindex übergeben bekommt.
In dem array steht entweder ein '-' oder eine Zahl, Also ist das Array bspw. -,-,4,1,2 die Methode soll dann rekursiv die Präfix-Notation lösen und das Ergebnis rausgeben.
Sprich in dem Fall also (4-1)-2 = 1

Mein Ansatz:

private int evaluateRecursively(char[] array, int startIndex) {

if(Character.isDigit(array[startIndex])) {
int firstValue = Character.getNumericValue(array[startIndex]);
evaluateRecursively(array, startIndex + 1);

}

else {
evaluateRecursively(array, startIndex + 1);

}

return ;
}

Aber ich hab absolut keine Ahnung wie ich weiter machen kann

 

[kneitzel]

Das Wichtige ist immer, dass man sich zuerst einen Algorithmus überlegt. Dabei spielt Java oder irgend eine andere Programmiersprache, absolut keine Rolle!

Wie ist denn so ein Präfix-Konstrukt denn auswertbar? Wie gehst Du denn vor, wenn Du das Array Auswertest? Also mit Stift und Papier.
Was machst Du wie? Was musst Du Dir ggf merken?

So lange wie Du keine klare Vorstellung von dem Code hast, ist es zu früh, auch nur eine Zeile Code zu schreiben.

 

[lenaS]

Ich hab mir dafür ein Baumdiagramm aufgemalt,
also ich prüfe den ersten Index, wenn dieser keine Zahl ist, schau ich mir den nächsten an, ist dieser ebenfalls keine Zahl, schau ich mir wiedern den nächsten an, usw.

Treffe ich das erste Mal auf eine Zahl, gehe ich weiter durch die Indizes, bis ich auf eine Zahl treffe, die ziehe ich dann von der ersten ab

So habe ich mir das vorgestellt🙈

 

[lenaS]

Das Wichtige ist immer, dass man sich zuerst einen Algorithmus überlegt. Dabei spielt Java oder irgend eine andere Programmiersprache, absolut keine Rolle!

Wie ist denn so ein Präfix-Konstrukt denn auswertbar? Wie gehst Du denn vor, wenn Du das Array Auswertest? Also mit Stift und Papier.
Was machst Du wie? Was musst Du Dir ggf merken?

So lange wie Du keine klare Vorstellung von dem Code hast, ist es zu früh, auch nur eine Zeile Code zu schreiben.

Ich hab mir dafür ein Baumdiagramm aufgemalt,
also ich prüfe den ersten Index, wenn dieser keine Zahl ist, schau ich mir den nächsten an, ist dieser ebenfalls keine Zahl, schau ich mir wiedern den nächsten an, usw.

Treffe ich das erste Mal auf eine Zahl, gehe ich weiter durch die Indizes, bis ich auf eine Zahl treffe, die ziehe ich dann von der ersten ab

So habe ich mir das vorgestellt🙈

 

[kneitzel]

Also das Problem ist ja, dass Du Dir die Operationen merken musst. Das können - sein aber doch auch alle anderen Operatoren.

Baumdiagram ist aber prinzipiell schon gut - Du hast also erkennt, dass eine Baumstruktur dahinter liegt.

Fangen wir einfach einmal klein an:

Wir geben das folgende Array rein: [ 5 ]
Was ist die Ausgabe? Rückgabe?

Edit: Ausgabe durch Rückgabe ersetzt. Der Begriff ist besser geeignet.

 

[kneitzel]

Oder um es als Baumstruktur zu sehen: Was ist, wenn ein Element eine Zahl enthält? Was zeichnet dieses Element des Baumes aus?

 

[lenaS]

Also das Problem ist ja, dass Du Dir die Operationen merken musst. Das können - sein aber doch auch alle anderen Operatoren.

Baumdiagram ist aber prinzipiell schon gut - Du hast also erkennt, dass eine Baumstruktur dahinter liegt.

Fangen wir einfach einmal klein an:

Wir geben das folgende Array rein: [ 5 ]
Was ist die Ausgabe? Rückgabe?

Edit: Ausgabe durch Rückgabe ersetzt. Der Begriff ist besser geeignet.

Die Rückgabe wäre in dem Fall 5, aber ich verstehe nicht ganz, was du meinst mit "Was zeichnet dieses Element des Baumes aus?"

In der Aufgabenstellung geht es erstmal nur um den - Operator

 

[kneitzel]

Wenn Du es als Baumstruktur aufmalst: Wie viele Child-Knoten hat jeder Knoten?

a) Wenn eine Operation vorhanden ist?
b) wenn eine Zahl vorhanden ist?

 

[lenaS]

Ich dachte eigentlich jeweils zwei, aber das scheint nicht zu stimmen.

 

[kneitzel]

Also bei der Operation stimmt das. Du hast bei der Operation eine feste Anzahl Operanden. Und bei - sind das 2. (Bei +, * und / wird das auch so bleiben. Es sind aber auch Operatoren mit nur einem Operanden denkbar: z.B, Wurzel, sin, cos, ....)
==> Operatoren haben eine feste / bei uns konkret 2 Childs!

Bei einer Zahl hatten wir eben ein Beispiel { 5 } -> Da hast Du keinerlei Childs.

Damit haben wir den einfachsten Fall sogar erledigt: Wenn das erste Element eine Zahl ist, dann ist das Ergebnis was? (Du hattest es für das Beispiel schon genannt: { 5 } => 5. bei { x } ist das Ergebnis also?

Dann kommt die Betrachtung der Operation. Wenn Du ein "-" hast, dann weisst Du, dass Du nach der Operation die Operanden hast:
{ -, (Elemente 1. Operand), (Elemente 2. Operand) }

Bei deinem Bespiel: { -, -, 4, 1, 2 }: Was sind die beiden Operanden des ersten -? (Sprich: Was für Child-bäume würdest du da finden?)

 

[lenaS]

Ach so, okay, das mit dem Beispiel {5} ergibt natürlich Sinn.

Die beiden Operanden des ersten - wären in dem Fall 4 und 1
dann hätte ich als ersten Zweig doch aber auch wieder, dass noch ein "-" kommt und als zweiten, die Möglichkeit einer Zahl

Tut mir leid, ich verstehe das noch nicht ganz :/

 

[kneitzel]

Die beiden Operanden des ersten - wären in dem Fall 4 und 1

Nein, das stimmt so nicht.

Du hast zuerst ein -, d.h. es kommen zwei Operanden.
Und der erste ist dann -, 4, 1
und der zweite ist die 2

Entsprechend sieht der Baum aus.

Hilft Dir dies nun, eine Operationsregel zu nennen?

a) Wenn es eine Zahl ist, dann wird die Zahl zurück gegeben.

b) Wenn es eine Operation ist, dann wird was gemacht?

Hier daran denken: Die Operatoren sind Teilbäume - also im Prinzip etwas, das wir ja schon machen ist da notwendig.

 

[lenaS]

Okay, also ich bin mir nicht ganz sicher, aber das bedeutet, dass wenn es eine Operation ist, dann ist der nächste Index Operand 1 und der darauffolgende Operand 2

Da bei dem Beispiel -, -, 4, 1, 2 nach dem ersten - noch eins kommt, wird da dann es nochmal durchgegenagen, sprich mit dem zweiten - setzt er 4-1 in Klammern und setzt es als Operand von dem ersten -

dabei ist 4 Operand1 von dem zweiten - und 1 der erste Operand des zweiten -

Stimmt das so?

 

[Neumi5694]

Nur als kleine Anmerkung, Kneitzel hilft dir ja eh schon gut weiter.
Ich find's toll, dass du das Ganze erst mal auf dem Papier (Stichwort Baumdiagramm) durchspielst, die meisten wollen immer sofort mit dem Kopf durch die Wand und klatschen dann als erstes Mal ein paar Schleifen hin. Weiter so.

 

[lenaS]

Nur als kleine Anmerkung, Kneitzel hilft dir ja eh schon gut weiter.
Ich find's toll, dass du das Ganze erst mal auf dem Papier (Stichwort Baumdiagramm) durchspielst, die meisten wollen immer sofort mit dem Kopf durch die Wand und klatschen dann als erstes Mal ein paar Schleifen hin. Weiter so.

Danke dir

 

[kneitzel]

Ja, Ich denke, Du hast es jetzt richtig verstanden.

Jetzt fehlt noch ein kleiner Schritt: Wir brauchen ja für die Berechnung der Differenz Zahlen. Was wäre das denn dann?

Wir haben ja jetzt sowas wie:
evaluateRecursively
- Nächstes Element eine Zahl? Ja: Zahl zurück geben.
- Nächstes Element ein "-": ja:
---> Erster Operand = ....
---> Zweiter Operand = ....
---> return erster Operand - zweiter Operand

Die Operanden kommen nacheinander als weitere Elemente ... Und wir wissen, die müssen ja auch wieder irgendwie ausgewertet werden ...
Und als ganz großer Wink mit dem Zaunpfahl: Es geht um eine Rekursion

 

[lenaS]

ALs ersten Operanden hätte ich die Funktion dann mit dem Index + 1 aufgerufen und als zweiten dann dementsprechend den auf den ersten Operanden folgenden Index

Würde das so stimmen?

 

[kneitzel]

Vergiss erst einmal den Index, dazu kommen wir gleich noch. Aber richtig: Wir sind dann jetzt bei etwas wie:

evaluateRecursively
- Nächstes Element eine Zahl? Ja: Zahl zurück geben.
- Nächstes Element ein "-": ja:
---> Erster Operand = evaluateRecursively
---> Zweiter Operand = evaluateRecursively
---> return erster Operand - zweiter Operand

Denn jetzt kommt das nächste Problem:
- Was gibt evaluateRecursively zurück?
- Was brauchen wir alles an Informationen?

Jetzt kommt auch der Index zum tragen. Spiel es mal mit dem Beispiel durch:
{ 0: -, 1: -, 2: 4, 3: 1, 4: 2 }
(Ich habe den Index mit index: jeweils davor geschrieben. Was wären denn die jeweils wichtigen Indices?)

Hier ist jetzt wichtig zu verstehen: Den Algorithmus in Form der Fragestellung "Wie läuft die Berechnung" haben wir fertig. Jetzt kommen Implementations-Probleme, die wir ggf. noch lösen müssen.

 

[lenaS]

evaluateRecursivly gibt ein Integer zurück, das Ergebnis aus allen Indizes berechnet
Das heißt, man müsste jetzt alle berechnungen speichern und zusammenrechnen, oder?

Sind nicht alle Indices wichtig?

 

[kneitzel]

Ja, aber das Problem ist doch, folgendes:
Du bist beim ersten -, also weisst Du: das folgende Zeichen ist der Start vom nächsten Teil. Aber du kannst nicht wissen, wie weit der Teil geht. Das kann ein Zeichen sein (wenn es eine Zahl wäre) oder beliebig viele (da kann ja noch mehr an Operationen kommen, die verschachtelt sind).

Daher brauchst Du auch noch eine Rückgabe, bei welchem index du denn gerade bist.

Aber java bietet nur eine Rückgabe und das macht es problematisch. Daher muss man hier etwas trixen:
Habt ihr abstrakte Datentypen wie Listen, Schlangen (Queue) und den stack behandelt?
Das würde es vereinfachen.

Ansonsten basteln wir uns eine kleine Hilfsklasse, die das abbildet, was wir brauchen.

 

[lenaS]

Listen ja, von Stack habe ich etwas gelesen, wir haben es aber nicht behandelt(wir dürfen es aber benutzen)

 

[kneitzel]

Ok, was wir brauchen ist eine Schlange / Queue. Wir wollen jedes Element einmal von Anfang bis Ende durchlaufen.

Der Unterschied zum Array ist: Bei der Schlange ist danach das Element, das wir gelesen haben, weg. Die Schlange verändert sich. Das Array würde aber gleich bleiben - und das wollen wir so natürlich nicht.

Damit haben wir also noch einen Kopf:
evaluateRecursively (Array)
==> Queue erstellen aus Array.
==> return evaluateRecursively(Queue)

Und den eigentlichen Algorithmus haben wir dann auch:
evaluateRecursively(Queue)
- nächstes Elemen = Element aus Queue entnehmen.
- Nächstes Element eine Zahl? Ja: Zahl zurück geben.
- Nächstes Element ein "-": ja:
---> Erster Operand = evaluateRecursively(Queue)
---> Zweiter Operand = evaluateRecursively(Queue)
---> return erster Operand - zweiter Operand

Damit haben wir dann erst einmal den Algorithmus erstellt. Kannst Du dem soweit folgen? Ist das verständlich gewesen?

Denn ein letzter Punkt fehlt noch:

Was ist mit diesen Fällen:
{ 5, 5 }
{ -, 4 }

Ist da irgendwas besonderes an diesen beiden Beispielen?

 

[lenaS]

Okay, vielen Dank!

Das Problem beim ersten Beipiel ist, dass wir keinen Operator haben, beim zweiten Beipiel ist ein Operand zu wenig, aber in der Aufgabenstellung wurde geschrieben, dass wir davon ausgehen können, dass dies bei den eingegeben Arrays nicht der Fall sein wird.

Auf jeden Fall vielen vielen Dank für alles!!
Ich habe jetzt noch eine Vorlseung und werde mich deswegen erst später noch einmal daran setzen können

Ich wünsche dir noch einen schnen ABend ! : )

 

[kneitzel]

Ok, dann müssen wir keine Fehler beandeln. Dann wären wir so weit, dass wir den Algorithmus haben und wir diesen nun implementieren könnten.

Danke auf jeden Fall für Deine Geduld - war angenehm, das einmal so durchzugehen. Ich hoffe, dass das Vorgehen halbwegs klar geworden ist - ansonsten ruhig nachfragen. Denn so ein Aufbau eines Algorithmus sollte Dir später wenn möglich auch gelingen.

 

[lenaS]

Ok, dann müssen wir keine Fehler beandeln. Dann wären wir so weit, dass wir den Algorithmus haben und wir diesen nun implementieren könnten.

Danke auf jeden Fall für Deine Geduld - war angenehm, das einmal so durchzugehen. Ich hoffe, dass das Vorgehen halbwegs klar geworden ist - ansonsten ruhig nachfragen. Denn so ein Aufbau eines Algorithmus sollte Dir später wenn möglich auch gelingen.

Danke für deine Geduld, es hat sehr geholfen, das von Grund auf durchzugehen

 

[berndoa]

Ich werf mal noch meine vermutlich unsinnige bzw. nicht so professionelle Idee rein:
Gegeben das Array , bspw. {-,*,1,2,3}
zuerst muss geprüft werden ob die Anzahl an Zeichen um 1 kleiner als die Anzahl an Zahlen ist.
Dann müsste man noch gucken ob das Ganze ein legitimer Ausdruck in präfixnotation (kein Ahnung wie genau).
Im nächsten Schritt würde ich die Position des ersten Zeichens suchen, der 2 Zahlen folgen.
im prinzip wertest du diesen Teilausdruck aus.
oben wäre das *,1,2, was zu 1*2=3 ausgewertet wird.

Dann würde ich ein eues Array mit einer um 2 kleineren Länge bauen, welches identishc zum vorherigen ist, aber halt *,1,2
durch 3 ersetzt wurde.
dann mit diesem neuen Array dasselbe machen.
Rinse and repeat bis das Array nur noch aus einer Zahl besteht.
Diese Zahl ist dann deine Antwort

 

[kneitzel]

Ich werf mal noch meine vermutlich unsinnige bzw. nicht so professionelle Idee rein:
Gegeben das Array , bspw. {-,*,1,2,3}
zuerst muss geprüft werden ob die Anzahl an Zeichen um 1 kleiner als die Anzahl an Zahlen ist.

Das ist eine möglich Validierung, die aber nicht wirklich viel aussagt zur Gültigkeit des Ausdrucks.
Wenn man den Ausdruck direkt auswertet, dann kommt man relativ schnell zu dem richtigen Ergebnis.

Dann würde ich ein eues Array mit einer um 2 kleineren Länge bauen, welches identishc zum vorherigen ist, aber halt *,1,2
durch 3 ersetzt wurde.

Du meinst natürlich 2 (1*2 = 2). Das ist übrigens ein funktionierender Ansatz, den man auch verallgemeinern kann:
Du gehst immer wieder durch die Liste, um dann einen Operator mit entsprechender Anzahl Operanden zu finden, die kein Operation sind und die werden dann ersetzt.

Das lässt sich übrigens auch sehr gut als Stack ausdrücken:
Du packst der Reihe nach immer alles auf den Stack. Der Stack prüft bei jedem Ablegen eines Elementes ob die obersten Elemente schon ausführbar sind. Ist dies der Fall, dann werden die Elemente vom Stack genommen, die Operation ausgeführt und das Ergebnis abgelegt.

Also bei deinem Beispiel: - * 1 2 3 wäre das:
-
- *
- * 1
- * 1 2 -> Ist jetzt ausführbar, also 2, 1 und * werden heraus genommen, es wird 1 *2 gerechnet und das Ergebnis auf den Stack gelegt: - 2
- 2 3 -> Ist auch ausführbar, also 3 2 und - werden heraus genommen und gerechnet und das Ergebnis kommt in den Stack: -1

Wenn alle Elemente abgelegt wurden, darf nur ein Element auf dem Stack sein und das wäre dann das Ergebnis. (Also eine Validierung findet automatisch statt, daher braucht es die Prüfung oben nicht)

Der grundsätzliche Ansatz ist aber auf jeden Fall in Ordnung. Nur eben leider ohne diese Anforderung zu erfüllen:

die Methode soll dann rekursiv die Präfix-Notation lösen

(Aber wir haben ja auch optimiert. Rekursiv wolltest Du vor gehen durch ständig neue Arrays, die Du baust. Hat aber dann leider eine Komplexität von O(n*n) fürchte ich, da du ggf. sehr oft durch das ganze Array durchgehen musst.)

 

[berndoa]

Das ist eine möglich Validierung, die aber nicht wirklich viel aussagt zur Gültigkeit des Ausdrucks.
Wenn man den Ausdruck direkt auswertet, dann kommt man relativ schnell zu dem richtigen Ergebnis.

Du meinst natürlich 2 (1*2 = 2). Das ist übrigens ein funktionierender Ansatz, den man auch verallgemeinern kann:
Du gehst immer wieder durch die Liste, um dann einen Operator mit entsprechender Anzahl Operanden zu finden, die kein Operation sind und die werden dann ersetzt.

Das lässt sich übrigens auch sehr gut als Stack ausdrücken:
Du packst der Reihe nach immer alles auf den Stack. Der Stack prüft bei jedem Ablegen eines Elementes ob die obersten Elemente schon ausführbar sind. Ist dies der Fall, dann werden die Elemente vom Stack genommen, die Operation ausgeführt und das Ergebnis abgelegt.

Also bei deinem Beispiel: - * 1 2 3 wäre das:
-
- *
- * 1
- * 1 2 -> Ist jetzt ausführbar, also 2, 1 und * werden heraus genommen, es wird 1 *2 gerechnet und das Ergebnis auf den Stack gelegt: - 2
- 2 3 -> Ist auch ausführbar, also 3 2 und - werden heraus genommen und gerechnet und das Ergebnis kommt in den Stack: -1

Wenn alle Elemente abgelegt wurden, darf nur ein Element auf dem Stack sein und das wäre dann das Ergebnis. (Also eine Validierung findet automatisch statt, daher braucht es die Prüfung oben nicht)

Der grundsätzliche Ansatz ist aber auf jeden Fall in Ordnung. Nur eben leider ohne diese Anforderung zu erfüllen:

(Aber wir haben ja auch optimiert. Rekursiv wolltest Du vor gehen durch ständig neue Arrays, die Du baust. Hat aber dann leider eine Komplexität von O(n*n) fürchte ich, da du ggf. sehr oft durch das ganze Array durchgehen musst.)

Mein problem mit einem Stack oer keller wäre halt dass das erste Minus nicht direkt verwertbar ist sondern die erste Auswertung erst beim Zeichen vor der ersten Zahl ist.

Da müsste ich erst eine menge Zeichen vom Stack runtehrolen und nebenhin legen bis ich an ein verwertbares Zeichen komme.

Aber klar, Alles auf einmal auszuwerten macht vermutlich mehr Sinn. Nur steige ich geistig bei maps, Binärbäumen und so nicht mehr allzu sehr durch

 

[kneitzel]

Da müsste ich erst eine menge Zeichen vom Stack runtehrolen und nebenhin legen bis ich an ein verwertbares Zeichen komme.

Nö, Du nimmst die Eingabe und legst Element für Element auf den Stack.

Bei jedem auf den Stack legen prüfst Du: Gibt es >= 3 Elemente und sind diese Auswertbar.

Das Prinzip ist so unter dem Strich identisch zu derPostfix Schreibweise. Da sieht man es aber viel schöner:

Postfix ist ja, dass der Operator nach den Zahlen kommt. Also das
+ 1 * 2 3
wäre ein
1 2 3 * +

Da ist das Vorgehen sehr einfach:
- Zahlen landen auf dem Stack
- Operatoren holen sich die Operanden vom Stack und das Ergebnis landet dann im Stack

Es wird also bei Postfix extrem einfach. Praefix ist von der Logik her nicht wirklich komplexer, aber man muss halt die obersten 3 Elemente vom Stack immer prüfen, was es halt schwerer lesbar macht.

Ich weiss nicht, ob diese Sichtweise / Umschreibung es etwas mehr verdeutlicht.

 

[fhoffmann]

Man kann das Problem auch mit Arrays lösen, wenn man sich die aktuelle Position im Array in der Klasse merkt, alo zum Beispiel:

    private int currentIndex;

    public int evaluate(char[] array) {
        currentIndex = 0;
        return evaluateRecursive(array);
    }

Dann muss man in der rekursiven Methode aber ein bisschen aufpassen, wann man diese Position erhöht.
Und man hat natürlich ein Problem, wenn die Methode mehrfach gleichzeitig aufgerufen wird.

 

[kneitzel]

Ja, wobei ich das mit dem Array zusammen in einer Klasse gakapselt hätte. Dann wäre das Problem mit parallelen Läufen auch erledigt (und wäre eine Art Queue wenn man so will).

 

[fhoffmann]

Ja, wobei ich das mit dem Array zusammen in einer Klasse gakapselt hätte. Dann wäre das Problem mit parallelen Läufen auch erledigt (und wäre eine Art Queue wenn man so will).

Es genügt auch, eine eigene Klasse zu haben, die nur ein int als Member hat.

 

[fhoffmann]

Ich habe es nun so gelöst:

    private class MyIndex {
        int pos = 0;
    }

    public int evaluate(char[] array) {
        MyIndex index = new MyIndex();
        return evaluateRecursive(array, index);
    }

    private int evaluateRecursive(char[] array, MyIndex index) {
        char currentChar = array[index.pos++]; // Hier kann eine ArrayIndexOutOfBoundsException fliegen
        // ...

 

[fhoffmann]

Es ist zwar hier verpönt, fertige Lösungen zu veröffentlichen, aber nachdem ich schon 3/4 des Codes hier eingestellt habe, kann ich ja auch die ganze Version bereitstellen (in einer Version, die davon ausgeht, dass der einzige Operator '-' ist; und die Klasse hat nicht zufällig die Endung "Kurz").

class PraefixNotationKurz {
    public static void main(String[] args) {
        System.out.println(new PraefixNotationKurz().evaluate(new char[] {'-', '-', '4', '1', '2'}));
    }
    private class MyIndex {
        int pos = 0;
    }
    public int evaluate(char[] array) {
        return evaluateRecursive(array, new MyIndex());
    }
    private int evaluateRecursive(char[] array, MyIndex index) {
        char currentChar = array[index.pos++];
        if(Character.isDigit(currentChar)) {
            return Character.getNumericValue(currentChar);
        } else { // if (currentChar == '-')
            return evaluateRecursive(array, index) - evaluateRecursive(array, index);
        }
    }
}

Der Trick ist die Klasse MyIndex, von der am Anfang eine Instanz erstellt wird, und deren Wert bei jedem Aufruf von evaluateRecursive um eins hochgesetzt wird; dadurch weiß jeder Aufgerufene, wo er im Array gerade suchen muss.