Autor |
Beitrag |
Sebo
Beiträge: 34
|
Verfasst: Di 11.01.05 16:05
Hallo Leute
Ich bin grad dabei ein Programm zuschreiben, welches mit Hilfe eines Kellerautomaten die Richtigkeit eines arithmetischen Terms erkennen soll. Falls der Term richtig ist, soll dieser danach ausgerrechnet werden. Ich hab bis jetzt nur einen endlichen Automaten entwickelt, welcher die Richtigkeit der Klammersetzung mit Hilfe einer Integer-Variable überprüft. Wie mach ich aus diesem Automaten einen Kellerautomat, wie kann ich dies dann programmiertechnisch umsetzen? Muss ich mir für das Ausrechnen des Terms ein Parser schreiben oder kann man dies dann auch in den Kellerautomat integrieren?
Komma = {'.',','}
Vorzeichen = {'+','-'}
Ziffer = {'0','1','2','3','4','5','6','7','8','9'}
Rechenzeichen = {'+','-','*','/'}
Klammer auf = {'('}
Klammer zu= {')'}
files.pre-grafix.de/sebo/imgs/automat.jpg
Quelltext dazu:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126: 127: 128: 129: 130: 131: 132: 133: 134: 135: 136: 137: 138: 139: 140: 141: 142: 143: 144: 145: 146: 147: 148: 149: 150: 151: 152: 153: 154: 155: 156: 157: 158: 159: 160: 161: 162: 163: 164:
| unit Unit1;
interface
uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls; const ziffern = ['0'..'9']; vorzeichen = ['+','-']; rechenzeichen = ['+','-','/','*']; klammerauf = ['(']; klammerzu = [')']; kommazeichen = [',','.']; type TForm1 = class(TForm) edterm: TEdit; btnok: TButton; lblausgabe: TLabel; procedure btnokClick(Sender: TObject); private public end; tZustand = (z0,z1,z2,z3,z4,z5,z6,z7,zf); var Form1: TForm1; zustand: tZustand; eingabezeichen: char; klammerkeller: integer;
implementation
{$R *.dfm}
function f(zustand: tZustand; x: char): tZustand; begin case zustand of z0 : if x in ziffern then f := z2 else if x in vorzeichen then f := z1 else if x in klammerauf then begin inc(klammerkeller); f := z6 end else f := zf; z1 : if x in ziffern then f := z2 else f := zf; z2 : if x in ziffern then f := z2 else if x in rechenzeichen then f := z5 else if x in kommazeichen then f := z3 else if x in klammerzu then if klammerkeller > 0 then begin dec(klammerkeller); f := z7 end else f := zf else f := zf; z3 : if x in ziffern then f := z4 else f := zf; z4 : if x in ziffern then f := z4 else if x in rechenzeichen then f := z5 else if x in klammerzu then if klammerkeller > 0 then begin dec(klammerkeller); f := z7 end else f := zf else f := zf; z5 : if x in ziffern then f := z2 else if x in klammerauf then begin inc(klammerkeller); f := z6 end else f := zf; z6 : if x in ziffern then f := z2 else if x in vorzeichen then f := z1 else if x in klammerauf then begin inc(klammerkeller); f := z6 end else f := zf; z7 : if x in rechenzeichen then f := z5 else if x in klammerzu then if klammerkeller > 0 then begin dec(klammerkeller); f := z7 end else f := zf else f := zf; zf : f := zf; end; end;
procedure TForm1.btnokClick(Sender: TObject); var pos: integer; s: string; begin s := edterm.Text; if length(s) > 0 then begin zustand := z0; pos := 0; klammerkeller := 0; while pos <> length(s) do begin zustand := f(zustand,s[pos+1]); inc(pos); end; if klammerkeller > 0 then zustand := zf; if (zustand = z2) or (zustand = z4) or (zustand = z7) then lblausgabe.caption := 'wahr' else lblausgabe.caption := 'falsch' end else lblausgabe.Caption := 'wahr'; end;
end. |
Danke für Eure Hilfe
Sebo
Moderiert von Christian S.: Code- durch Delphi-Tags ersetzt.
|
|
MathiasH
Beiträge: 699
WinXP, Win98SE, Debian, Win95
D5 Stand, D6 Prof
|
Verfasst: Di 11.01.05 18:55
wen du mir jetzt noch erzählst, was ein Kellerautomat ist...
Parser schreiben ist an sich net schwer.
a) rekursiv: term von hinten und vorne zugleich durchgehen, jeden gefundenen unterterm rekursiv auswerten
b) iterativ term von vorne nach hinten auswerten, ergebnisse in de stack legen (pop/push)
_________________ "Viel von sich reden, kann auch ein Mittel sein, sich zu verbergen."
Friedrich Nietzsche
|
|
Sebo
Beiträge: 34
|
Verfasst: Di 11.01.05 19:32
Hab mal die genaue Defintion rausgesucht:
de.wikipedia.org/wiki/Kellerautomat
Zitat: | arser schreiben ist an sich net schwer.
a) rekursiv: term von hinten und vorne zugleich durchgehen, jeden gefundenen unterterm rekursiv auswerten
b) iterativ term von vorne nach hinten auswerten, ergebnisse in de stack legen (pop/push) |
Jo einen Parser hab ich schon fast fertig. Der ist jedoch nach "Methode" a) gestrickt.
Ich glaub der Kellerautomat ist das gleiche wie "Methode" b). Kannst du b) noch etwas genauer erklären.
|
|
|