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

[shmia]

Es macht wenig Sinn, eine eigene Stack-Klasse zu programmieren, wenn es das schon gibt.
(==> das Quadratische Rad neu erfinden)
In der Unit contnrs gibt es die Klassen:
TStack, TQueue, TObjectQueue, TObjectStack, ...
Diese Klassen sind fehlerfrei und ein guter Ausgangspunkt.

[sirius]

Zitat:

Es macht wenig Sinn, eine eigene Stack-Klasse zu programmieren, wenn es das schon gibt.

Der Sinn liegt evtl. im Üben

@Preddy:
Was willst du eigentlich genau:
-einen Stack simulieren/programmieren
-einen Matheparser schreiben

Prinzipiell sind in deiner Stackklasse ein paar Ungereimtheiten und es könnte bei POP wenn der Stack leer wird zu einer EA kommen.
Speicherlöcher dürften nicht entstehen.

[Preddy2005]

Danke für die Antworten.

Ist mir aber prinzipiell egal, ob es das bereits schon gibt... Dann bin ich halt ein sogenannter Antipattern Mensch.
Ich will den Stack als Lerneffekt programmieren... Später will ich dann das Ganze auf einen Matheparser ausbauen.
Der soll erstmal nur einfach Dinge tun...

Sind die Stackklassen von Delphi denn brauchbar??
Ich programmiere Dinge lieber selbst um dabei auch was zu lernen...
Von Copy & Paste halt ich nämlich persönlich überhaupt nix.

Gruß Matthias

[CalganX]

Hi,
warum machst du es so umständlich über Zeiger? Du kannst es dir einfach machen, indem du ein dynamisches Array nimmst, dass du füllst. Dann kannst du ganz einfach über Array[index] darauf zugreifen. Außerdem kannst du dann noch viel einfacher mit Move den ganzen Stack bewegen, wenn du Elemente rauspopst oder reinpusht.
Ich denke, dass verkettete Listen an dieser Stelle viel zu überflüssig sind.

Zu deiner zweiten Frage: eigentlich sollte alles auf einem Stack liegen. Infix heißt, dass der Operand vor den Zahlen kommt: + 3 5 wäre ein Beispiel dafür. D.h. beim Tokenizing wirst du erst die beiden Werte ablegen und dann den Operanden. Beim Parsen kommt dann erst der Operand. Dann weißt du ja auch, wie viele Parameter du aus dem Stack holen musst. Also z.B. "!" (Fakultät) erwartet ja nur einen Parameter. (Nachtrag: Postfix ist ja das Gleiche nur anders herum.)
Noch eine Anmerkung zu deinem Beispiel: das Auswerten des Terms hat in der Stack-Klasse nichts zu suchen. Die Stack-Klasse hat erstmal nur die Aufgabe den Stack zu verwalten. Was da drin passiert, ist nicht Aufgabe der Stack-Klasse.

Generell empfiehlt sich die Lektüre von Anleitungen zum Compilerbau, damit du das Prinzip verstehst und weißt, was Tokenizing, lexikalische/syntaktische/semantische Analyse und Parsen genau bedeutet. Das Thema kommt zwar "schon" im Grundstudium Informatik dran, aber grundsätzlich sollte man nicht glauben, dass man das ohne viel Wissen mal eben so runter schreiben kann.

Chris

[mr47]

@CalganX: Wenn du aber ein Element einfügst, ist das bei Listen viel schöner, da du nur 2 (oder vielleicht auch 4) Zeiger ändern musst.
Ich weiß nicht wie dieses Move beim Array arbeitet, aber wenn das alles einen Speicherblock weitergeschoben wird ist das ziemlich Arbeits-/Zeitaufwändig für den Prozess.


edit: Rechtschreibung

[CalganX]

Und wenn ich von außen ein Element ändere oder sonst irgendwie der Zeiger ungültig wird, ist meine Liste kaputt. Super.
Gut, ich gebe zu, dass ich bisher nicht viel mit verketteten Listen gemacht habe, aber ich wollte in erster Linie auch nur anregen, dass es eine Alternative gibt, die eigentlich relativ einfach ist.

Code-technisch ist Move eine Zeile. Wie schnell oder langsam das letztlich zur Laufzeit ist, kann ich dir auch nicht sagen, aber ich würde sagen, dass bei meinem Parser für eine Assembler-Emulation der Flaschenhals ein anderer, als der Stack ist.

Außerdem ist der Sinn eines Stacks ja, dass man nur die Elemente ganz oben verändern kann. D.h. man kann auf das Move auch problemlos verzichten:

Delphi-Quellcode:

procedure TStack.Push(AValue: integer);
begin
  SetLength(FData, Length(FData)+1);
  FData[Length(FData)-1] := VAlue;
end;

function TStack.Pop: integer;
begin
  Result := FData[Length(FData)-1];
  SetLength(FData, Length(FData)-1);
end;

Mehr sollte ein Stack ja auch eigentlich nicht brauchen. Auf jeden Fall kein "in der Mitte einfügen".

Chris

[mr47]

Zitat von CalganX:

Außerdem ist der Sinn eines Stacks ja, dass man nur die Elemente ganz oben verändern kann. D.h. man kann auf das Move auch problemlos verzichten:

Natürlich! Ich war gedanklich gerade so bei meiner doppelt verketteten Liste, dass ich ganz vergaß worum es geht Es ist natürlich absoluter unsinn bei einem Stack ein Element einzufügen!

[Christian Seehase]

Moin Chris,

wobei es der Performance zuträglich wäre, von vornherein eine bestimmte Stackgrösse vorzugeben, und dann Push/Pop mittels Stackpointer (bei einem Array dann halt ein Index), auf die Stackelemente zuzugreifen, statt jedesmal mit SetLength die Grösse zu verändern. Das würde jedenfalls Push beschleunigen.
Wenn der Stack denn eine dynamische Grösse haben soll, prüft man vorher, ob der Platz noch reicht, und vergrössert ihn dann um einen Wert (z.B. 10%)

[Preddy2005]

Ich lese jetzt hier die ganze Zeit nur von dynamischen Arrays. Sind diese nun für die Stack Programmierung besser geeignet als die doppelte verkettete Liste?

Was ich noch nicht verstanden habe, ein Stack für alle Zahlen und Operatoren. Soll man den Stack dann quasi nur aus Strings bestehen lassen und die Werte vom Stack holen?
Diese dann anschließend konvertieren?
Oder soll man dann besser mit selbst definierten Konstanten arbeiten?

Muss ich mir wiklich Anleitungen für den Compilerbau angucken?
Habe schon viel über den Bau von Compilern gelesen aber Theorie und Praxis ist halt nicht das Gleiche und somit hänge ich bei Realisierung ein wenig fest.

Gruß Matthias