Stack Programmierung

[Preddy2005]

Hallo erstmal!

Wollte mich auch mal dran machen einen einfachen Parser zu schreiben und habe deshalb mich über den ganzen Prozess informiert.

Habe allerdings noch ein paar Fragen, weil mir bestimmte Schritte noch nict ganz klar geworden sind und ich hoffe man kann mir hier im Forum helfen...

1) Ist der unten liegende Code korrekt mit der Speicherverwaltung der doppelten verketteten Liste ? Weil mit Memproof zeigt er an,
das wohl der Speicher nicht komplett freigegeben wird... Tue mich noch etwas schwer mit den Pointer Geschichten, aber was nicht
ist, das kann noch werden.

Delphi-Quellcode:

{*******************************************************************************
********************************************************************************

     Stackklasse, welche die Funktionalität des Stacks veranschaulicht

                  Erstellt am 14.03.2007 Matthias Lorenz

{*******************************************************************************
*******************************************************************************}

unit Stack;

interface

uses classes, sysutils;

{*******************************************************************************
                       // Typen für die Stackklasse
*******************************************************************************}

type TZeichen = (PLUS,MINUS,MAL,GETEILT);
type TZahlen  = (NULL,EINS,ZWEI,DREI,VIER,FUENF,SECHS,SIEBEN,ACHT,NEUN);

type Zeiger = ^Stack_Speicher;

Stack_Speicher = Record
   Wert    : Integer;
   Next    : Zeiger;
   Prev    : Zeiger;
end;

{*******************************************************************************
                             // Stack Klasse
*******************************************************************************}

type TStack = class(TObject)
private
 FStackAnfang   : Zeiger;
 FNeuesElement  : Zeiger;
 FStackTop      : Zeiger;
 FStackCount    : Integer;

public

Constructor Create;
Destructor  Destroy; override;
procedure   Push (Element : Integer);
function    Pop () : Integer;
function    Top () : Integer;
function    Stack_Elemente_Anzahl () : Integer;
function    Infix_Postfix ( Text : String ) : String;

end;

implementation

{*******************************************************************************
*******************************************************************************}

{ Stack }

constructor TStack.Create;
begin
 FStackCount  := 0;
 FStackAnfang := Nil;
end;

{*******************************************************************************
*******************************************************************************}

destructor TStack.Destroy;
var Neues_Letztes_Element : Zeiger;
begin // Liste durchlaufen, bis der Prev- Zeiger auf Nil zeigt ( Listenende )
 if (FStackTop = nil) then exit;
  Neues_Letztes_Element := FStackTop;

   while (Neues_Letztes_Element.Prev <> nil) do
    begin
     Neues_Letztes_Element       := FStackTop^.Prev;
     Neues_Letztes_Element^.Next := nil;
     Dispose(FStackTop);
     FStackTop := Neues_Letztes_Element;
    end;

end;

{*******************************************************************************
*******************************************************************************}

function TStack.Pop() : Integer; // Vom Stack löschen
var Neues_Letztes_Element : Zeiger;
begin
 result := 0;
 if ( FStackCount = 0 ) then
 begin
  result := 0;
  exit;
 end;

  if ( FStackCount = 1 ) then // Nur wenn noch 1 Element auf dem Stack
   begin
    result := FStackTop^.Wert;
    Dispose(FStackAnfang);
    FStackAnfang^.Next := nil;
    FStackAnfang^.Prev := nil;
    FStackAnfang := nil;
    FStackTop := FStackAnfang;
    FStackCount := 0;
   end
    else
     begin // Ansonsten oberste Element auf dem Stack entfernen }

      if ( FStackTop.Prev = nil ) then
       begin
        FStackTop := FStackAnfang;
        exit;
       end;
        result := FStackTop^.Wert;
        Neues_Letztes_Element := FStackTop^.Prev;
        Neues_Letztes_Element^.Next := nil;
        Dispose(FStackTop);
        FStackTop   := Neues_Letztes_Element;
        FStackCount := FStackCount - 1;
     end;

end;

{*******************************************************************************
*******************************************************************************}

procedure TStack.Push(Element: Integer); // Auf den Stack legen
begin
  if ( FStackCount = 0 ) then // Sonderfall ( Erstes Element )
   begin 
    New(FNeuesElement);
    FStackAnfang := FNeuesElement;
    FStackAnfang^.Wert := Element;
    FStackAnfang^.Next := Nil;
    FStackAnfang^.Prev := Nil;
    FStackTop     := FStackAnfang;
    FStackCount   := FStackCount +1;
   end
    else // Sonst nur Elemente verknüpfen
     begin
      New(FNeuesElement);
      FNeuesElement^.Next := Nil;
      FNeuesElement^.Prev := FStackTop;
      FNeuesElement^.Wert := Element;
      FStackTop^.Next     := FNeuesElement;
      FStackTop           := FNeuesElement;
      FStackCount         := FStackCount +1;
     end;
end;

{*******************************************************************************
*******************************************************************************}

function TStack.Stack_Elemente_Anzahl: Integer;
begin
 result := FStackCount;
end;

{*******************************************************************************
*******************************************************************************}

function TStack.Top(): Integer;
begin // Oberstes Element zurückliefern
 result := 0;
  if ( FStackCount = 1 ) then result := FStackAnfang^.Wert;
   if ( FStackCount > 1 ) then result := FStackTop^.Wert;
end;

{*******************************************************************************
*******************************************************************************}

2) Ich habe gelesen, das man den Stack für die Speicherung benutzt und der String in Postfix Notation abgespeichtert wird.
Hat man zwei seperate Stacks ( Zahlen ) und ( Operanden) oder nur einen Stack?
Dann legt man alle Elemente via Push auf dem Stack ab und kombiniert diese, bis man das Ergebnis hat.

Reichen für diesen Zweck Pos Funktionen aus?

Wie sieht so eine Umwandlung aus? Aus den ganzen fertigen Parsern bin ich nicht schlau geworden?

Delphi-Quellcode:

function TStack.Infix_Postfix(Text: String): String;
var Term : String;
    i : Integer;
    Zahl1, Zahl2, Ergebnis : Double;
    Zahlenmenge : Shortint;

begin
 Zahlenmenge := 0;
 Term := StringReplace(Text,' ','',[rfReplaceAll]);
 result := Term;

 for i := 1 to Length(Term) do
  begin

     // Prototyp [ sollte auch mit in [ 0..9] funktionieren
    case (Term[i]) of
     '1': Push(1);
     '2':
       begin
        Push(2);
        Zahlenmenge := Zahlenmenge + 1;
       end;
     '3': Push(3);
     '4':
      begin
       Push(4);
       Zahlenmenge := Zahlenmenge + 1;
      end;
     '5': Push(5);
     '6': Push(6);
     '7': Push(7);
     '8': Push(8);
     '9': Push(9);
    end;


    if ( Zahlenmenge = 2 ) then
     begin

     // Prüfen, welcher Operator im Term vorhanden ist
    case (Term[i]) of
     '+':
      begin
       Zahl2 := Pop();
       Zahl1 := Pop();
       Ergebnis := Zahl1 + Zahl2;
       result   := FloattoStr(Ergebnis);
      end;
     '-':
      begin
       Zahl2 := Pop();
       Zahl1 := Pop();
       Ergebnis := Zahl1 - Zahl2;
       result   := FloattoStr(Ergebnis);
      end;
     '*':
      begin
       Zahl2 := Pop();
       Zahl1 := Pop();
       Ergebnis := Zahl1 * Zahl2;
       result   := FloattoStr(Ergebnis);
      end;
     '/':
      begin
       Zahl2 := Pop();
       Zahl1 := Pop();
       Ergebnis := Zahl1 / Zahl2;
       result   := FloattoStr(Ergebnis);
      end;
    end;
  end;

     end;

Der obige Code ist jetzt einfach mal so als Grundgerüst gebaut worden... Ohne wirkliche Funktionalität... Ist das so in etwas korrekt mit dem auswerten?

Ich weiss es sind eine Menge Fragen, aber wer nicht fragt bleibt dumm...
Praxis und Theorie sind halt doch 2 verschiedene Welten.

Danke im voraus für die Hilfe...

Gruß Matthias