Stack: Infix nach Postfix und push und pop

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

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;