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;

[Khabarakh]

Zu Infix2Postfix: Kann es sein, dass der Algorithmus nur für sehr spezielle Terme gedacht ist? Bei "(5 + 6)", "(1 + (2 * 3))" etc. würde er nämlich funktionieren. Für gewöhnliche Terme bleibt der Algo leider nicht so trivial ;) .
/edit: Gut, da bin ich mit himitsu wohl einer Meinung :) .

Zu CalcPostfix: Schau dir das mal im Debugger an, da wird beim Leerzeichen eine 0 gepusht ;) . Verschiebe push(x) in den "0-9"-Block, die beiden anderen kannst du gleich in push(pop + pop) bzw. push(pop * pop) umschreiben.

[Luckie]

Zitat:

Zitat von himitsu

Der Operator wird nur bei ) aus dem Stack geholt

Wer dnekt denn an so was? Als Beispieleingabe war gegeben: 5*(((9+8)*(4*6))+7).

Zitat:

dubnibel

Was? Was bedeutet dubnibel :mrgreen:

Zitat:

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

Ups. Korrigiert.

@Khabarakh: Das habe ich auch gesehen. Aber ich habe jetzt den aktuellen Code von himitsu.

So funktioniert es jetzt wie es soll. Jetzt muss ich ihn nur noch verstehen. @himitsu: Könntest du zu deinem Code noch ein paar erklärende Worte verlieren?

Danke euch allen schon mal. Und keine Angst, das wird kein Rechner oder Matheparser. Das ist nur für ein weiteres Kapitel in meinem Listen Artikel.

PS: Als nächstes geht es um FIFO Stacks. Die werden dort als Schlangen bezeichnet. Wie nennt man die auf Englisch? Snakes? Klingt komisch. :grübel:

[himitsu]

ich schreib gleich noch was dazu

FIFO Stacks = Queue

FIFO Stacks (first in - first out) = Queue = oben drauflegen - unten rausziehen
FILO Stacks (first in - last out) = Stack = oben drauflegen - oben runternehmen

PS: http://www.delphipraxis.net/internal...t.php?t=167796 ist praktisch alles in einem
stack = z.B. push + pop oder shift + unshift
queue = z.B. push + unshift oder shift + pop

(ich weiß, so ist das irgendwie etwas vewirrend, wenn man nur auf die Namen schaut, aber von deren Funktion her sollte es klar sein)

[Luckie]

Schön. Dank dir. Sind, was im Buch als Schlangen bezeichnet wird, im Original also queues. Ich hatte andauernd snake oder so im Kopf. :mrgreen:

Lass dir Zeit. Ich gucke jetzt so wie so erst mal Formel 1 mit dem Schumi, der im falsch lackiertem Auto sitzt. ;)

[Luckie]

Zitat:

Zitat von himitsu

ich schreib gleich noch was dazu

Kleine Erinnerung. ;)

[himitsu]

Zitat:

Zitat von Luckie

Kleine Erinnerung. ;)

*herzinfakt bekomm*

jaaa, ich nehm mir gleich mal ein minütchen.
(schon schlimm, wenn man morgen schon wegfährt und sich kurzfristig ergeben hat, daß ein Übernachtungstag wegfällt, man aber dennoch diese Nacht in 'ner fremden Stadt zubringen müßte ... hatte grade nur mal kurz zur Ablenkung etwas in der DP reingesehn)

[edit]
ach du sch***, das dubnibel war ja von mir. :shock:

*überleg* ... ich glaub es könnte/sollte "du noch" oder irgendwie sowas heißen :gruebel:


[add]
@Luckie: um welchen Teil geht es denn vorzugsweise?

Nicht daß ich hier jetzt anfang jede Zeile einzeln zu kommentieren. :stupid:

[Luckie]

Es geht eigentlich nur um deine beiden Funktionen.

[himitsu]

Dabei macht der Code doch eigentlich nichts Anderes?
Außer daß die Schittstellen der Ein- und Ausgabe umgestellt wurde.

Statt READ wird jetzt nacheinander ein Zeichen aus dem String genommen
und anstatt WRITE wird der Text an den Result-String angehängt.
OK, für ein nachfolgendes EOL wird nun vorher die aktuelle Zeichenpostition über LENGTH geprüft.

// dein Code aus Post #1
{} nachfolgend jeweils der entsprechende Befehl aus Pst #10

Delphi-Quellcode:

function Infix2Postfix(const S: String): String;
var
  i: Integer;
begin
  Result := '';
//Init;
{}init;
//repeat
{}i := 1;
{}while i <= Length(S) do begin
  //repeat read(c) until c <> ' ';
  {}if S[i] <> ' ' then begin
    //if c = ')' then write(chr(pop));
    {}if S[i] = ')' then Result := Result + chr(pop);
    //if c = '+' then push(ord(c));
    {}if S[i] = '+' then push(ord(S[i]));
    //if c = '*' then push(ord(c));
    {}if S[i] = '*' then push(ord(S[i]));
    //while (c >='0') and (c<='9') do
    //  begin write(c), read(c); end;
    {}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 c <> '(' then write (' ');
    {}if (i <= Length(S)) and (S[i] <> '(') then Result := Result + ' ';
  {}end;
//until eoln;
{}  Inc(i);
{}end;
end;

function CalcPostfix(const S: String): String;
var
  i, x: Integer;
begin
  Result := '';
//Init;
{}init;
//repeat
{}i := 1;
{}while i <= Length(S) do begin
  //x := 0;
  //repeat read(c) until c <> ' ';
  {}if S[i] <> ' ' then begin
  {}  x := 0;
    //if c = '*' then x := pop*poop;
    {}if S[i] = '*' then x := pop * pop;
    //if c = '+' then x := pop+pop;
    {}if S[i] = '+' then x := pop + pop;
    //while (c >= '0') and (c <= '9') do
    //begin
    //  x := 10*x+(ord(c)-ord('0'));
    //   read(c);
    //end;
    {}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);
    {}push(x);
  {}end;
//until eoln;
{}  Inc(i);
{}end;
//writeln(pop);
{}Result := Result + IntToStr(pop);
end;

[Luckie]

Ah, OK. Danke. jetzt muss ich mir nur noch mal die push und pop Routinmen angucken und verstehen. Dann kann ich endlich meinen Artikel fertig schreiben.