Stack: Infix nach Postfix und push und pop

[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.