Umgekehrte Polnische Notation / Postfix-Notation über Stack programmieren, so richtig?
Hallo,
ich soll die umgekehrte polnische Notation / Postfix-Notation in Java mit Hilfe eines Stacks programmieren. Dafür stehen mir nur folgende Informationen zur Verfügung:
public class IntegerStack {
public boolean emptystack();
public int head();
public void push(int i);
public int pop();
}
Leider zeigt ein Testfall als Fehler Folgendes an:
IntegerStack s = new IntegerStack();
String[] input = {"1", "2", "*", "3", "4", "*", "+"};
Calculator(input, s);
System.out.println(s.compareHistory(new String[] {
"[1]",
"[1, 2]",
"[1]",
"[]",
"[2]",
"[2, 3]",
"[2, 3, 4]",
"[2, 3]",
"[2]",
"[2, 12]",
"[2]",
"[]",
"[14]",
"[]" }
));
// erwartet:
true
// erhalten:
wrong history length: target 14 - is 0
false
Ich kann diesen Fehler nicht deuten. Kann mir bitte jemand sagen, was da falsch sein soll? Ich weiß nicht, was ich beheben soll.
Anbei mein Code:
public int Calculator(String[] input, IntegerStack s) {
s = new IntegerStack();
for (int i = 0; i < input.length; i++) {
switch(input[i]) {
case "+":
int x = s.pop();
int y = s.pop();
s.push(y + x);
break;
case "-":
x = s.pop();
y = s.pop();
s.push(y - x);
break;
case "/":
x = s.pop();
y = s.pop();
s.push(y / x);
break;
case "*":
x = s.pop();
y = s.pop();
s.push(y * x);
break;
case " ":
break;
default:
if (input[i] != null) {
s.push(Integer.parseInt(input[i]));
}
else {
}
;
}
}
int z = s.pop();
return z;
}
3 Antworten
Nur am Rande, Du brauchst die Werte nicht in Variablen zu holen, ein s.push(s.pop()+s.pop()) etc. funktioniert genauso gut.
Das an die History COmpare Funktion übergebene String Array ist 14 Elemente lang, die interne History demnach vorgeblich 0. Warum das so ist könnte man lediglich sagen, wenn man die Implementierung des Stacks kennen würde.
Ah, da liegt der Hund begraben: Im Calculator reinstanziierst Du s, Du solltest aber natürlich den übergebenen Stack nehmen, dessen compare methode danach aufgerufen wird ;-).
Vorab: alle else-Zweige in Calculator() sind falsch. Macht hier aber nix, weil y==0 im Test nie auftritt.
Ich vermute (wegen "target length = 14"), dass der erste Eintrag in der Stack-History der Startzustand "[]" ist. Das fehlt in Deinem Vergleichs-Array.
Autsch! Der Fehler liegt in der ersten Zeile von Calculator() :
s = new IntegerStack()
Damit überschreibst Du den Funktionsparameter. Der übergebene Stack bleibt damit unbenutzt und leer.
Lösch diese Zeile.
Der default-Zweig ist nicht das Problem. Ich meinte das hier:
System.out.println(s.compareHistory(new String[] {
"[]", // <==== Startzustand
"[1]",
Warum triffst Du bei allen Operationen die Unterscheidung ob y != 0 ist oder nicht?
Das dürfte zu Fehlern führen, denn Du machst ja dann drei pops auf dem Stack anstatt nur zwei.
Danke für die Antwort, auch ohne Fallunterscheidung klappt es nicht. Ich hatte gedacht, eine Fallunterscheidung sei nötig, um die leeren Felder zu eliminieren, hatte die daher im Nachhinein ergänzt. Hat nichts gebracht.
Die Anzahl an pops war jedoch trotzdem immer nur 2x
*anzahl an pops war jedoch trotzdem für den Testfall unerheblich, leider, sonst wäre es gelöst :)
Konnte es nicht mehr bearbeiten, meinte folgendes als Satz: *anzahl an pops war jedoch trotzdem für den Testfall unerheblich, leider, sonst wäre es gelöst :)
Hast du sonst eine weitere Vermutung, woran der Fehler liegen kann?
Nee, ist überhaupt nicht unerheblich! Du machst nämlich dann einen POP auf dem leeren Stack.
Hast Du mal den Debugger verwendet um genau zu sehen, was passiert?
Mein Debugger hat nicht funktioniert bzw. nichts rausgespuckt.
Der spuckt auch nichts aus - Du setzt einen Breakpoint, gehst dann im Einzelschritt durch den Code und schaust, was in den Variablen steht.
Kann ich nicht mehr nachvollziehen, weil die Fragestellung geändert wurde. Aber sei's drum - die Frage, ob das Ding richtig rechnet, lässt sich durch einen Breakpoint und Variable Inspection ganz einfach beantworten.
ob das Ding richtig rechnet
Dazu muss man eigentlich nur die push() und pop() im Code zählen :-)
Danke für die Antwort. Wie kann man das beheben? Ich habe es versucht mit if(input[i] == null) {s.push(0); } in der default Anweisung-> hat leider nicht geklappt.