Stack: Infix nach Postfix und push und pop

[Luckie]

Ich versuche gerade das Beispiel für Stapel aus meinem Algorithmenbuch nach zu vollziehen. Mut dem Push und Pop Routinen habe ich noch Verständnis Probleme, was da passiert. Und ich habe Probleme mit dem Pascal Code aus dem Buch.

Der Stack (Ich habe schon die Variablen etwas sinnvoller benannt):

Delphi-Quellcode:

type
  PStackElement = ^TStackElement;
  TStackElement = record
    data: Integer;
    next: PStackElement;
  end;

var
  FirstElement: PStackElement;
  LastElement: PStackElement;

procedure Init;
begin
  New(FirstElement);
  New(LastElement);
  FirstElement.next := LastElement;
  LastElement.next := LastElement;
end;

procedure push(data: Integer);
var
  ElementToPush: PStackElement;
begin
  New(ElementToPush);
  ElementToPush.data := data;
  ElementToPush.next := FirstElement.next;
  FirstElement.next := ElementToPush;
end;

function pop: Integer;
var
  ElementToPop: PStackElement;
begin
  ElementToPop := FirstElement.next;
  Result := ElementToPop.data;
  FirstElement.next := ElementToPop.next;
  Dispose(ElementToPop);
end;

Infix nach Postfix:

Delphi-Quellcode:

Init;
repeat
  repeat read(c) until c <> ' ';
  if c = ')' then write(chr(pop));
  if c = '+' then push(ord(c));
  if c = '*' then push(ord(c));
  while (c >='0') and (c<='9') do
    begin write(c), read(c); end;
  if c <> '(' then write (' ');
until eoln;

Ausrechnen eines Postfix-Ausdruckes:

Delphi-Quellcode:

Init;
repeat
  x := 0;
  repeat read(c) until c <> ' ';
  if c = '*' then x := pop*poop;
  if c = '+' then x := pop+pop;
  while (c >= '0') and (c <= '9') do
    begin x := 10*x+(ord(c)-ord('0')); read(c); end;
  push(x);
until eoln;
writeln(pop);

Mit den letzten beiden Routinen komme ich gar nicht klar. Ich habe sie mal genauso abgetippt wie sie im Buch stehen inklusive Formatierung. Variablendeklarationen sind im Buch auch nicht gegeben. Wie würden diese beiden Routinen als Delphi Funktionen aussehen? Also ich würde beiden Funktion eine Zeichenkette übergeben. Die erste Routine liefert mir dann eine Postfix Zeichenkette zurück und die zweite Routine das Ergebnis als Integer.

[Namenloser]

Hab mal auf die Schnelle die zweite Routine in eine Funktion gepackt und etwas standardkonformer formatiert (aber ungetestet):

Delphi-Quellcode:

function Eval(PostFix: string): integer;
var
  i: integer;
  x: integer;
  c: char;
  procedure NextChar(var c: char);
  begin
    inc(i);
    if i <= length(PostFix) then
      c := PostFix[i]
    else
      c := #0;
  end;
begin
  i := 0;
  repeat
    x := 0;

    repeat 
      NextChar(c) 
    until c <> ' ';

    case c of
      '*': x := pop*pop;
      '+': x := pop+pop;
      { ... }
    end;

    while (c >= '0') and (c <= '9') do
    begin 
      x := 10*x + (ord(c) - ord('0')); 
      NextChar(c); 
    end;

    push(x);
  until c = #0;
  Result := pop;
end;

Hilft dir das weiter?

[Luckie]

Hm. Muss ich mir mal genauer angucken. Im Augenblick steige ich da noch nicht so ganz durch deinen Code durch. Wenn ich da 56+ eingebe gibt er mir 0 aus. Das hat mir auch schon der Originalcode ausgegeben. Jetzt ist natürlich die Frage, ob mein Stackcode fehlerhaft ist.

Aber man muss ja erst mal den Infix Ausdruck nach Postfix umwandeln mit Hilfe meiner Stack Implementation.

[Namenloser]

Hier mal ein etwas älterer Postfixparser von mir. Er kann zwar nicht unbedingt mit der schlichten Eleganz des Beispielscodes mithalten, aber dafür ist er einigermaßen objektorientiert :mrgreen: Das Umwandeln von Postfix in Infix hatte ich damals allerdings weggelassen, weil ich den Algorithmus von Wikipedia nicht ganz verstanden habe.

Im Konsolenfenster wird übrigens nach jedem Rechenschritt der aktuelle Stack angezeigt, was vielleicht zum besseren Verständnis auch ganz hilfreich ist.

[Luckie]

Danke für dein Programm. Aber ich wollte eigentlich schon den original Code aus dem Buch umsetzen und verstehen.

[Klaus01]

Guten Morgen 'Schlaflos in Kassel' (Luckie),

die Routine aus dem Buch liest die Eingabe von der Kommandozeile,

Delphi-Quellcode:

Init;
repeat
  repeat read(c) until c <> ' ';     // Lese bis ein Zeichen kein Leerzeichen ist
  if c = ')' then write(chr(pop));   // bei ')' hole ein Zeichen vom Stack
  if c = '+' then push(ord(c));
  if c = '*' then push(ord(c));
  while (c >='0') and (c<='9') do   // Verarbeite Zeichen von '0' bis '9';
    begin write(c), read(c); end;
  if c <> '(' then write (' ');
until eoln;

In Delphi würde ich die Eingabe als Zeichenkette erwarten
und die if durch case ersetzen.

Delphi-Quellcode:

function infix2postfix(infixStr: AnsiString):AnsiString;
var
  i: Byte;
begin
  init;
  result := '';
  for i:= 1 to length(infixStr) do
    begin
      case inifixStr[i] of
        ')' : result := result + chr(pop);
        '+' : push(ord(infixStr[i]);
        '*' : push(ord(infixStr[i]);
        '0'..'9' : result := result + infixStr[i]; 
        '(' : result := result + ' ';
    end;
end;

Grüße
Klaus

[himitsu]

Zitat:

Wenn ich da 56+ eingebe gibt er mir 0 aus.

Du müßtest dort '5 6 +' eingeben ... halt so wie '123 456 +', denn so wäre es als Infix '56 + unbekannt' und dieser nicht grade fehlerresistente/fehlererkennende Code reagiert da offenbar nicht sehr optimal.

Zitat:

Zitat von Luckie

Mut dem Push und Pop Routinen habe ich noch Verständnis Probleme, was da passiert.

http://de.wikipedia.org/wiki/Stapelspeicher

Push fügst einen Wert an oben in einer Liste ein und Pop holt den obersten Wert wieder aus der Lieste raus.


Als Funktion umgestellt könnte es eventuell so aussehn:

Delphi-Quellcode:

function Infix2Postfix(const S: String): String;
var
  i: Integer;
begin
  Result := '';
  init;
  i := 1;
  while i <= Length(S) do begin
    if S[i] <> ' ' then begin
      if S[i] = ')' then Result := Result + chr(pop);
      if S[i] = '+' then push(ord(S[i]));
      if S[i] = '*' then push(ord(S[i]));
      while (i <= Length(S)) and (S[i] >= '0') and (S[i] <= '9') do begin
        Result := Result + c;
        Inc(i);
      end;
      if (i <= Length(S)) and (S[i] <> '(') then Result := Result + ' ';
    end;
    Inc(i);
  end;
end;

Delphi-Quellcode:

function CalcPostfix(const S: String): String;
var
  i, x: Integer;
begin
  Result := '';
  init;
  i := 1;
  while i <= Length(S) do begin
    if S[i] <> ' ' then begin
      x := 0;
      if S[i] = '*' then x := pop * pop;
      if S[i] = '+' then x := pop + pop;
      while (i <= Length(S)) and (S[i] >= '0') and (S[i] <= '9') do begin
        x := 10 * x + (ord(S[i]) - ord('0'));
        Inc(i);
      end;
      push(x);
    end;
    Inc(i);
  end;
  Result := Result + IntToStr(pop);
end;

und noch ein bissl umgestellt käme z.B. sowas raus:

Delphi-Quellcode:

function Infix2Postfix(const S: String): String;
var
  i: Integer;
begin
  Result := '';
  init;
  for i := 1 to Length(S) do
    case S[i] of
      ')': Result := Result + chr(pop);
      '+': push(ord(S[i]));
      '*': push(ord(S[i]));
      '0'..'9': Result := Result + c;
    end;
end;

Delphi-Quellcode:

function CalcPostfix(const S: String): String;
var
  i, x: Integer;
begin
  Result := '';
  init;
  i := 1;
  while i <= Length(S) do begin
    x := 0;
    case S[i] of
      '*': x := pop * pop;
      '+': x := pop + pop;
      '0'..'9': begin
        x := ord(S[i]) - ord('0');
        while (i < Length(S)) and (S[i + 1] >= '0') and (S[i + 1] <= '9') do begin
          Inc(i);
          x := 10 * x + (ord(S[i]) - ord('0'));
        end;
      end;
    end;
    push(x);
    Inc(i);
  end;
  Result := Result + IntToStr(pop);
end;

[ot]
Jetzt bastelt auch noch der Luckie an einem Taschenrechner. :shock:
Wann kommt denn der BF-Interpreter?

[DeddyH]

Zitat:

Zitat von himitsu

[ot]
Jetzt bastelt auch noch der Luckie an einem Taschenrechner. :shock:
Wann kommt denn der BF-Interpreter?

Gleich nach dem Memory ;)

[Luckie]

Danke für eure Mühe, insbesondere himitsu. Allerdings gibt es da ein kleines Problem:

Delphi-Quellcode:

function Infix2Postfix(const S: String): String;
var
  i: Integer;
begin
  Result := '';
  init;
  for i := 1 to Length(S) do
    case S[i] of
      ')': Result := Result + chr(pop);
      '+': push(ord(S[i]));
      '*': push(ord(S[i]));
      '0'..'9': Result := Result + S[i];
    end;
end;

function CalcPostfix(const S: String): String;
var
  i, x: Integer;
begin
  Result := '';
  i := 1;
  while i <= Length(S) do begin
    x := 0;
    case S[i] of
      '*': x := pop * pop;
      '+': x := pop + pop;
      '0'..'9': begin
        x := ord(S[i]) - ord('0');
        while (i < Length(S)) and (S[i + 1] >= '0') and (S[i + 1] <= '9') do begin
          Inc(i);
          x := 10 * x + (ord(S[i]) - ord('0'));
        end;
      end;
    end;
    push(x);
    Inc(i);
  end;
  Result := Result + IntToStr(pop);
end;

Bei der Umwandlung von Infix nach Postfix geht das Rechenzeichen verloren. aus 5 + 6 wird nur 56. das hat natürlich zur Folge das CalcPostfix nix macht. ;)

Aufruf:

Delphi-Quellcode:

  Init;
  Readln(s);
  s := Infix2Postfix(s);
  Writeln(s);
  Init;
  s := CalcPostfix(s);
  Writeln(s);
  Readln;

Eingabe:

Code:

5 + 6

Aber auch wenn ich CalcPostFix

Code:

5 6 +

übergebe, bekomme ich als Ausgabe nur 6.

Da ist also noch irgendwo der Wurm drin. Kann natürlich auch an meinem Stack liegen, dass der fehlerhaft ist, siehe oben.

[himitsu]

Kein Wunder, daß es nicht geht.

Delphi-Quellcode:

if S[i] = ')' then
        Result := Result + chr(pop);

Der Operator wird nur bei ) aus dem Stack geholt, also müßtest dubnibel jede Operation mit Klammern versehn.
(dieses Verhalten war aber auch schon im Originalcode so :shock: )

PS: Du hast ein Speicherleck, da im Init ein Element in den Stack geschoben, aber nicht wieder rausgeholt wird.

Delphi-Quellcode:

type
  PStackElement = ^TStackElement;
  TStackElement = record
    data: Integer;
    next: PStackElement;
  end;

var
  FirstElement: PStackElement;
  LastElement: PStackElement;

procedure Init;
begin
  New(FirstElement);
  New(LastElement);
  FirstElement.next := LastElement;
  LastElement.next := LastElement;
end;

procedure push(data: Integer);
var
  ElementToPush: PStackElement;
begin
  New(ElementToPush);
  ElementToPush.data := data;
  ElementToPush.next := FirstElement.next;
  FirstElement.next := ElementToPush;
end;

function pop: Integer;
var
  ElementToPop: PStackElement;
begin
  ElementToPop := FirstElement.next;
  Result := ElementToPop.data;
  FirstElement.next := ElementToPop.next;
  Dispose(ElementToPop);
end;

function Infix2Postfix(const S: String): String;
var
  i: Integer;
begin
  Result := '';
  init;
  i := 1;
  while i <= Length(S) do begin
    if S[i] <> ' ' then begin
      if S[i] = ')' then
        Result := Result + chr(pop);
      if S[i] = '+' then
        push(ord(S[i]));
      if S[i] = '*' then
        push(ord(S[i]));
      if (S[i] >= '0') and (S[i] <= '9') then begin
        Result := Result + S[i];
        while (i < Length(S)) and (S[i + 1] >= '0') and (S[i + 1] <= '9') do begin
          Result := Result + S[i];
          Inc(i);
        end;
      end;
      if (i <= Length(S)) and (S[i] <> '(') then
        Result := Result + ' ';
    end;
    Inc(i);
  end;
end;

function CalcPostfix(const S: String): String;
var
  i, x: Integer;
begin
  Result := '';
  init;
  i := 1;
  while i <= Length(S) do begin
    if S[i] <> ' ' then begin
      x := 0;
      if S[i] = '*' then
        x := pop * pop;
      if S[i] = '+' then
        x := pop + pop;
      if (S[i] >= '0') and (S[i] <= '9') then begin
        x := ord(S[i]) - ord('0');
        while (i < Length(S)) and (S[i + 1] >= '0') and (S[i + 1] <= '9') do begin
          x := 10 * x + (ord(S[i]) - ord('0'));
          Inc(i);
        end;
      end;
      push(x);
    end;
    Inc(i);
  end;
  Result := Result + IntToStr(pop);
end;

procedure TForm1.FormCreate(Sender: TObject);
var
  S: String;
begin
  S := '(5 + 6)';
  S := Infix2Postfix(S);
  S := CalcPostfix(S);
  ShowMessage(S);
end;