Stack: Infix nach Postfix und push und pop

[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 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.
Wann kommt denn der BF-Interpreter?