Arrays mit drei Dimensionen... nicht einfach -.-

[ArchaicSeraphim]

Hi Leutz,

Ich habe ja in der vergangenen Zeit viele Fragen zu arrays bzw. Automaten gestellt... ^^ Hier kommt die wahrscheinlich letzte: Wie kann ich drei Variablen in einem dynamischen Array speichern? Ich brauche ja die Zustände, den Kellerzustand und die Eingabe. Und dann muss dieses Array auch zwei Sachen ausgeben: Neuer Zustand und Kelleroperation.

Bsp.: Wenn ich überprüfen lassen will, ob ein eingegebener Term dem Muster A^n*B^n entspricht, kann ich Zeichen für Zeichen vorgehen und habe dann die vier Zustände zS (Start- und Zielzustand), zA (mehr As als Bs), zB (mehr Bs als As) und zF (Fehlerzustand, aus dem man nie wieder raus kommt). Das Problem ist aber, dass ich jeden dieser Zustände noch aufteilen muss, je nachdem, ob in meinem Stack/Keller schon eine Marke, die Startmarke oder nichts liegt. Und wie gesagt müsste die Ausgabe ja auch beinhalten a) den neuen Zustand und b) die Kelleroperation -push, pop oder nop - z.B. wenn ein A kommt, ich im Zustand zB bin und nur eine Marke auf dem Stack liegt: zS|pop.

Wie kann ich sowas machen? Ich krieg's einfach nicht in mein Hirn. Ohne den Keller wäre das einfacher, dann könnte man einfach ein Array array[Zustand, Eingabe] of NeuerZustand machen. Das wäre quasi die Automatentabelle.
Kann mir einer helfen, das auch mit drei Dimensionen zu schaffen? pls?

Danke schon mal, falls das ginge *unterwürfig*

[edit=Jelly]
Es geht um diesen Keller
Nächstes Mal bitte selbst editieren... :warn:
Mfg, Jelly[/edit]

[CK_CK]

Hi,
was hälst du denn von einem Array mit einem Record?

Delphi-Quellcode:

TElement = record
  variable1: String;
  variable2: Integer;
end;

var
  arr: array of TElement;

Chris

EDIT: Ich glaube, ich hab' dich falsch verstanden... Wie wäre es, wenn du zu dem Thread mit der "Keller-Frage" verlinkst?

[mkinzler]

Dafür würde ich einen Record deklarieren.
Mehrdimensional Array kann man aber leicht anlegen:

Delphi-Quellcode:

   myarray: Array of array of String;

oder

Delphi-Quellcode:

type  
   sarray = Array of string;
...
var
   myarray: Array of sarray;

[Jelly]

Keller
Stack
Marke

:roteyes: :roteyes: :roteyes:

Nix comprende, compadre :wall:

EDIT: Verlinke bitte in deinem ersten Beitrag auf den anderen Keller Thread... So blickt ja kein Mensch durch worums geht.

[ArchaicSeraphim]

Link hier.

Aber ich brauche ja quasi drei Dimensionen. array of array wäre doch nur 'ne Tabelle, oder?

[CK_CK]

Und Array of Array of Array wäre eine 3D-Matrix ;)

Aber ich hab' dein Problem immer noch nicht verstanden... :stupid:

Chris

[mkinzler]

Überleg dir das noch mal mit dem Record.

Delphi-Quellcode:

myarray: array of array of array of string;

[ArchaicSeraphim]

Naja, ich muss wissen, in welchem Zustand der Automat sich befindet, welchen Kellerzustand der Keller hat, und welche Eingabe getätigt wurde, um den Neuen Zustand und die Kelleroperation festlegen zu können. Inhaltlich musstes ja gar nicht verstehen, nur wie progge ich mir das zusammen?

Hlp pls!

[CK_CK]

Wie gesagt, mit einem Record:

Delphi-Quellcode:

TKeller = record
  Zustand: Integer;
  Kellerzustand: Integer;
  Eingabe: String;
end;
...
var
  Kellerelemente: array of TKeller

Chris

[mkinzler]

Einen Stack (Keller) implementiert man besser mit einer Liste. Brauchst du den Zustand an einer bestimmten Position der Liste oder nur den aktuellen?

[Jelly]

Ich weiss immer noch nicht was dein Keller ist, welche Operationen es da gibt, und schon gar nicht das im Zusammenhang steht. Erklär dich mal bitte, das hier bringt nix.

Ich hab das Gefühl, du willst die ganze Logik unbedingt in ein Array packen. Die Frage ist, ob das sinnvoll ist. Es bietet sich eventuell eher eine objektorientierte Lösung an. Aber dafür müssen wir erst einmal dein Problem verstehen.

[ArchaicSeraphim]

Also:

• Automat: Maschine, die innere Zustände hat, und je nach Zustand unterschiedlich auf Eingaben reagiert.
  
• Kellerautomat: Automat, der noch einen Zähler/Stack/Keller miteingebaut hat.

Den braucht man, wenn man z.B. sowas machen will wie überprüfen, ob alle geöffneten Klammern auch geschlossen wurden. Der einfache Automat weiß ja nicht, wieviele geöffnete Klammern es gibt. Der bräuchte quasi unendlich Zustände. Deshalb hat ein schlauer Mensch den Stack/Keller erfunden. Da ist eine Startmarke (s) drin, man kann andere Marken rein-"push"en (m, die Operation heißt 'push'), die oberste angucken (top) und rausschmeißen (pop) bzw. nichts machen (nop). Die Frage ist jetzt, wie kann ich alle diese Infos (Zustand, Eingabe, Kellerzustand und -operation) miteinander kombinieren? Von mir aus auch nicht in einem Array. Aber W-I-E?
Ich raff's net... :wall:

[mkinzler]

Man gibt hier Tipps und Anstösse am laufenden Band. Doch du ignorierst diese einfach.

[ArchaicSeraphim]

Hmm... Ich werde mal was dazu schreiben: Was ist ein Record? Sry, ich habe keine Ahnung. Hab' ich nie gelernt *schäm*

Und mit einem array of array geht das doch nicht, oder? Ich habe ja nicht alle Fälle abgedeckt. Ich brauche ja quasi so eine Tabelle:

Code:

Zustände  Kellerzustände  Eingaben   |   neue Zustände  Kellerops
                                     
zB.       Das hier soll alles                         
          "Input" sein.                              
                                     |
A           s                1       |        B             push
            m                2       |        A             pop
            s                2       |        A             pop
            m                1       |        B             push
                                     |
                                     |
B           s                1       |        A             pop
            m                2       |        B             pop
            s                2       |        B             push
            m                1       |        A             push
                                     |

Klar soweit?

[DeddyH]

Ein Record ist quasi eine Klasse ohne Methoden (man vergebe mir diese laxe Beschreibung).

[mkinzler]

http://www.delphipraxis.net/internal...=805632#805632

[ArchaicSeraphim]

Eine Klasse ohne Methoden? Also sowas wie... ein Memo, nur halt keine GUI? So in die Richtung?

€dit: Wie soll ich die Kellerzustände und -operationen denn getrennt speichern? Und wie kann ich sowas auslesen? oO

[mkinzler]

Eine Record ist eine Struktur. Man nennt. Im Unterschied zum Array kann man hier verschiedene Typen mischen und adressiert nicht per Index sondern per Namen.

[ArchaicSeraphim]

OK, aber weiterhin: Wie kann ich die Kelleroperationen aus dem Record auslesen und dann anwenden? Kann ich sagen "Keller.(Record.Kelleroperationen)" (Keller sei hierbei mein Kellerobjekt)? Geht sowas?

[DeddyH]

Anders ausgedrückt: man verwendet einen Record, wenn man zusammenhängende Daten braucht, die sich aus Einzeldaten zusammensetzen.
Beispiel: eine Adresse

Delphi-Quellcode:

type TAdresse = record
  Name, 
  Vorname, 
  Strasse, 
  Hausnummer, 
  PLZ, 
  Ort: string;
end;

(Das könnten auch verschiedene Datentypen sein und nicht nur String)
Wenn Du nun eine Variable vom Typ TAdresse definierst, kannst Du über die Punkt-Methode wie bei einer Klasse auf die einzelnen Felder zugreifen. Für mehr Infos schau mal in die Hilfe, ich bin zu faul für mehr Details ;)

[edit] end vergessen :oops: [/edit]

[mkinzler]

Delphi-Quellcode:

Keller[<Index>].Kellerzustand

[ArchaicSeraphim]

Records sind aber nicht dynamisch oder? Ich müsste dann ja dynamisch Cards anlegen, stimmt das? Kann man das auch umgehen? :oops:

mkinzler, kannst du das

Delphi-Quellcode:

Keller[<Index>].Kellerzustand

auch mal erklären, pls? Ich bin halt schwer von Begriff... :pale:

[mkinzler]

Delphi-Quellcode:

var
    Kellerelemente: array of TKeller;
   zustand: Integer;
...
  //Zustand des Rootelements
  zustand := Kellerelemente[0].Kellerzustand;

Records sind nicht dynamisch

[ArchaicSeraphim]

Wieso machst du das array variabel? Die Automatentabelle beschreibt doch das "Verhalten" des Automaten, also sollte sie fest sein. Da will ich ja quasi eintragen was bei Eingabe X und Zustand Y und Kellerzustand Z für ein neuer Zustand Y' und Kelleroperation k rauskommt.

Sorry, das ich euch so nerve. -.- Ich bin halt langsam... ;]

[mkinzler]

Also du hast einen Stack und eine definierte Anzahl von Zuständen und für jeden Zustand verschiedene Eingabekombinationen (2 Parameter) und daraus resultierende Aktionen auf dem Stack und Folgezustände?

[ArchaicSeraphim]

Ganz genau so schaut's aus!

€dit: Leute, sorry, ich geh' jetzt mal pennen, ich muss den morgigen Tag noch überstehen xD Bis denne! ^^

[mkinzler]

Dann sollten wir die Struktur etwas ändern. Zuerst würde ich den Array durch eine Liste oder besser durch eine fertige Stack-Klasse ersetzten

Delphi-Quellcode:

unit Stack;

interface

uses
  SysUtils, Classes;

type
  TStack = class
  private
    FList: PPointerList;
    FCapacity, FCount: Cardinal;
    procedure Grow;
  public
    destructor Destroy; override;
    procedure Push( const Data: Pointer );
    function Pop: Pointer;
  end;

implementation

{ TStack }

destructor TStack.Destroy;
begin
  FreeMem( FList );
  inherited;
end;

procedure TStack.Grow;
begin
  if FCapacity > 64 then
    Inc( FCapacity, FCapacity div 4 )
  else
    if FCapacity > 8 then
      Inc( FCapacity, 16 )
    else
      Inc( FCapacity, 4 );
  ReallocMem( FList, FCapacity * SizeOf( Pointer ) );
end;

function TStack.Pop: Pointer;
begin
  if FCount > 0 then
  begin
    Dec( FCount );
    Result := FList^[FCount];
  end
  else
    Result := nil;
end;

procedure TStack.Push(const Data: Pointer);
begin
  if FCapacity = FCount then
    Grow;
  FList^[FCount] := Data;
  Inc( FCount );
end;

end.

Deklaration von Konstanten für die Operationen:

Delphi-Quellcode:

const
    action_push=0;
    action_pop=1;

Record für Zustände:

Delphi-Quellcode:

TZustaende = Record
   Name: string;
   Input1: char;
   Input2: Integer;
   Folgezustand: String;
   Operation: byte;
end;

Du Zustaende würde ich auch in einer Liste verwalten

[alzaimar]

ArchaicSeraphim, ich glaube, Du vermischt hier zwei Dinge:

Zum einen benötigst Du vermutlich einen Stack (Keller), und zum Anderen eine Zustandsübergangstabelle. Der Keller hat aber mit der Übergangstabelle nichts zu tun.

Für die Übergänge (Y',Z') bei Eingabezeichen X, Zustand Y und Kellerzustand Z) verwendest Du ein statisches 3D-'Array of TÜebergang', so etwa:

Delphi-Quellcode:

Type
  TEingabezeichenklasse = (ezA, ezB, ezIllegal);              // Dein Alphabet
  TZustand = (zsNeutral, zsMehrAalsB, zsMehrBalsA, zsFehler); // Deine DEA-Knoten
  TKellerZustand = (kzA, kzB);                                // Deine Kellerzustände, kann aber Quark sein

  TUebergang = Record
    ZustandNeu : TZustand;
    KellerzustandNeu : TKellerZustand;
  End;

  TZustandsuebergangstabelle = Array [TEingabezeichenklasse,TZustand, TKellerZustand] Of TUebergang;

Sei nun ZT so eine Tabelle, e das Eingabezeichen, z der aktuelle Zustand und k der aktuelle Kellerzustand, dann findest Du den nächsten Zustand so:

Delphi-Quellcode:

Var
  ZT : TZustandsuebergangstabelle;
  e : TEingabezeichenklasse;
  z : TZustand;
  k : TKellerzustand;

Begin
 ...
 DerNeueZustand := ZT[e,z,k].ZustandNeu;
 DerNeueKellerzustand := ZT[e,z,k].KellerzustandNeu;
...

[mr_emre_d]

edit: hehe, mein beitrag war fehl am platz... :freak:
:wall:

[ArchaicSeraphim]

Hoi Leutz,

Sorry, mkinzler, aber dein Modell trifft leider nicht ganz das, was ich brauche, denn das ist ja der Stack/Keller, den ich schon programmiert habe. Ich brauche ja noch den Automaten, der einen Stack benutzt.

Dein Ansatz gefällt mir, alzaimar. Aber was soll das mit

Delphi-Quellcode:

TUebergangstabelle = array [TEingabe,TZustand,TKellerZustand] of TUebergang;

? Ist das eine Variable?

Vielen Dank schon mal, viel Hilfe von euch hilft mir, Leute! Weiter so, pls!

[mkinzler]

Ich habe dir nur eine alternative, bessere Implementierung für den Stack geliefert.
Der Rest meines Vorschlags ging ja in die selbe Richtung wie alzaimars.

[ArchaicSeraphim]

Hmm, na dann, danke mkinzler. Aber ich kann das überhaupt nicht benutzen, das ist auf einem so hohen Niveau... ich verstehe zwar ein paar Sachen, aber die meisten Befehle kenne ich nicht und insgesamt ist das total gruselig gut xD
Zu gut für meine Durchschnittsprodukte :oops:

€dit: Kann mir auch mal wer sagen, wie ich diese Übergangstabeller mit Werten füllen kann? Ich will die mal als Konstante vorgeben. Die liegt dann ausgelagert in einer Unit "Tabelle1" oder so. Damit man auch verschiedene Automatentafeln benutzen kann. Das Problem ist jetzt, wie fülle ich ein dreidimensionales Array mit 'nem Record drin? Wie fülle ich überhaupt 'nen Record? So:

Delphi-Quellcode:

UeT : TUebergangstabelle =
(((NZustand:=zsA,NKellerZustand:=kA),({...usw}),({usw...})),
  ({usw...}),({usw...}));

?

Geht das? Hilfe!

[alzaimar]

Fast richtig. Einfach die Werte eintragen, ohne 'Namen'.

Delphi-Quellcode:

Const
  UT : TUebergangstabelle = (
   (a1,b1,c1),
   (a2,b2,c2)
...
   );

[ArchaicSeraphim]

Öh... hä? :wiejetzt: Ich bin ehrlich verwirrt... Ich dachte, in dem Record werden zwei Sachen gespeichert, muss man dann nicht auch immer zwei Werte eintragen? Also sozusagen

Delphi-Quellcode:

Const 
  UT : TUebergangstabelle = ( 
   ((a1,b1),(c1,d1)), 
   ((a2,b2),(c2,d2)) 
... 
   );

?

[alzaimar]

Du weisst schon, was ich meine.... Probier halt mal rum.

[ArchaicSeraphim]

Hehe, ok, ich probier dann mal rum. Wenn's (wieder, heul) Probleme geben sollte melde ich mich. Wenn's klappt schalte ich die Frage auf beantwortet ;]

€dit: Aha, hab' schon ein Problem: Wie kann ich denn eine Methode in einem Record speichern / auslesen? Ich will ja nicht den neuen Kellerzustand in dem Record haben, sondern die Kelleroperation.

[ArchaicSeraphim]

Sorry für den Doppelpost, bin so ungeduldig.

Wie kann ich in dem Record eine Methode des Kellers speichern bzw. auslesen?

€dit:

So sieht mein Krempel bis jetzt aus:

Delphi-Quellcode:

unit Automat;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, Keller;

type
  TAutomat = class
    constructor create;
    function proof(input:char):boolean;
  end;
  TEingabe = (eA,eB,eI);
  TZustand = (zS,zA,zB,zF);
  TKellerZustand = (s,m);
  TUebergang = record
    NZustand:TZustand;
    Kellerops:integer;
  end;
  TUebergangstabelle = array [TEingabe,TZustand,TKellerzustand] of (TUebergang.NZustand,TUebergang.Kellerops);


const
  UeT : TUebergangstabelle = (
        (((zA),(1)),((zB),(1)),((zF),(0))),             // Keller: s   zS
        (((zF),(0)),((zF),(0)),(zF,(0))),               //         s   zA
        (((zF),(0)),((zF),(0)),(zF,(0))),               //         s   zB
        (((zF),(0)),((zF),(0)),(zF,(0))),               //         s   zF
        (((zF),(0)),((zF),(0)),(zF,(0))),               //         m   zS
        (((zA),(1)),((zA),(-1)),(zF,(0))),              //         m   zA
        (((zB),(-1)),((zB),(1)),(zF,(0))),              //         m   zB
        (((zF),(0)),((zF),(0)),(zF,(0))),               //         m   zF
        );

var
  e : TEingabe;
  z : TZustand;
  k : TKellerzustand;
  AKeller : TKeller;
  AUebergang : TUebergang;

implementation

constructor create;
begin
  inherited create;
  AKeller := TKeller.create;
  z := zS;
  k := s;
end;

function proof(input:char):boolean;
var
i,n: integer;
begin
  n := length(input);
  for i := 1 to n do
  begin
    e := input[i];
    AUebergang
  end
end;

end.

Wo ist der Fehler? HILFE!!!

[ArchaicSeraphim]

Hab' das Problem gelöst. Sry für den Tripelpost xD