also wir sollen einen Taschenrechner programmieren der auf einem Kellerautomaten beruht. Ich hab schon rausgefunden, dass man mit dem Kellerautomaten den String der Rechnung (z.B. „4*(3+2)“) auf Richtigkeit überprüfen kann, also ob die Zeichen zulässig sind und ob die Klammern richtig gesetzt wurden usw… aber weiter komm ich nicht… wie kann ich den Term denn tatsächlich berechnen mit dem Kellerautomaten??
Hat jemand da nen Lösungsansatz?
Keine Lösung, aber …
Also ich muss zugeben, dass ich das Wort „Kellerautomat“ bis heute nicht kannte. Was es nicht alles gibt … 
Und wenn ich bei Google mal „Kellerautomat“ eingebe und mir nur Seiten auf Deutsch zurückgeben lasse, kommen ein paar Seiten, die den mehr oder weniger verständlich beschreiben.
Als Nicht-Fachmann verstehe ich das nun so, dass Du vor allem die Klammer-Ausdrücke identifizieren kannst. Aber auch die Berechnungs-Symbole sollten erkennbar sein.
Ich vermute mal, dass man sich ein Set aus Symbolen und Operatoren definieren muss, also () + - * / ^ und so weiter und für jedes dieser Symbole einen eigenen Keller-Automaten braucht. Allerdings läuft das am Ende doch auf einen einzigen hinaus, der allerdings auf verschiedene Symbole „reagiert“. Für jeden Operator brauchst Du dann eine separate Berechnungs-Routine.
Ich glaube, Dein Verständnisproblem ist, dass Du Struktur und Berechnung nicht auseinander hältst. Der Automat ist meines Erachtens ausschließlich zum PARSEN da, also zum Erkennen und Identifizieren von Strukturen (hier also Zahlen, Klammern und Operanden). Die Berechnung hingegen ist davon unabhängig und findet sozusagen in den Zuständen bzw. Zustandsübergängen des Automaten statt (Informatiker werden mich jetzt erhängen).
Ich stelle mir das so vor, dass der Automat, wenn er eine Bedingung als gegeben erkannt hat (z.B. eine schließende zur öffnenden Klammer gefunden hat), das, was darin als Argument enthalten ist, an die nächst höhere Ebene der Verarbeitung weitergibt. Ohje, das klingt doof. Nehmen wir mal die Addition. Der Automat liest einen Ausdruck und dann ein +. Das Plus kommt in den Stack und wird wieder gelöscht, wenn der nächste Operand gelesen wurde (weil das Plus zwei Operanden erwartet). Diese Lösch-Aktion vom Stack muss nun die Berechnung anstoßen, wozu die beiden Operanden natürlich irgendwo gespeichert worden sein müssen. Die Punkt-vor-Strich-Regel stellt hier allerdings eine kleine Herausforderung dar …
Naja, wie gesagt, das ist nicht fachlich fundiert und ist nur ein Versuch, Denkanstöße zu geben. Manchmal hift das, die eigenen Gedanken zu sortieren.
Viele Grüße,
Kristian
PS (nicht ganz ernst gemeint): Du kannst ja mal fragen, ob Ihr auch die Umgekehrte Polnische Notation (RPN) implementieren könnt 
Das ist vielleicht einfacher, weil es ohne Klammern auskommt. Ist eine feine Sache, wenn man sich daran gewöhnt hat. Der HP 48 G funktioniert nach dem Prinzip (keine Ahnung, ob der überhaupt noch erhältlich ist, aber ich glaube, der hat einen Nachfolger).
Ebenfalls keine Lösung, aber …
… schau mal unter www.wikipedia.de „Kellerautomat“ nach, da ist Funktionsweise, Beispiel und sogar ein teilweise Hilfreicher Quelltext abgelegt.
Hallo,
Also ich muss zugeben, dass ich das Wort „Kellerautomat“ bis
heute nicht kannte.
„Keller“ ist ein Germanismus für „Stack“.
Was es nicht alles gibt …
ich bei Google mal „Kellerautomat“ eingebe und mir nur Seiten
auf Deutsch zurückgeben lasse, kommen ein paar Seiten, die den
mehr oder weniger verständlich beschreiben.
Und eine Seite, wo der Fragesteller die selbe Frage noch in einem anderen Forum gestellt hat. An dieser Stelle habe ich die Lust verloren , mich weiter mit dem Thema zu beschäftigen.
Ich stelle mir das so vor, dass der Automat, wenn er eine
Bedingung als gegeben erkannt hat (z.B. eine schließende zur
öffnenden Klammer gefunden hat), das, was darin als Argument
enthalten ist, an die nächst höhere Ebene der Verarbeitung
weitergibt. Ohje, das klingt doof.
Das klingt nicht doof, das ist Rekursion. Wenn man Rekursion verwendet kann man sogar auf einen Stack verzichten. Ich finde, das ist hier ganz gut beschrieben:
http://compilers.iecc.com/crenshaw/
(Im wesentlichen in dem Kapitel über Interpreter).
Grüße,
Moritz
… schau mal unter www.wikipedia.de „Kellerautomat“ nach, da
ist Funktionsweise, Beispiel und sogar ein teilweise
Hilfreicher Quelltext abgelegt.
Das ist schon richtig, und die Seite kam auch bei den besagten Google-Ergebnissen. Aber hier fehlt wie bei allen anderen Seiten der Berechnungs-Aspekt. Deshalb ja meine Vermutung, dass man Paren und Berechnen voneinander trennen muss und der Kellerautomat mit letzterem nicht viel zu schaffen hat.
Und die formalen Definitionen, die man auch überall findet … naja … also das ist was für Theoretiker und Klausuren Und für welche, die´s ganz genau wissen wollen. Hilft hier aber nicht wirklich weiter
„Keller“ ist ein Germanismus für „Stack“.
Naja, dass es kein Automat ist, der nur im Keller aufgestellt werden kann, war mir klar Kleiner Scherz.
Und eine Seite, wo der Fragesteller die selbe Frage noch in einem anderen Forum gestellt hat.
Genau den habe ich dann wohl übersehen. Und? Gab´s da ´ne erschöpfende Antwort? Vielleicht von Dir?
An dieser Stelle habe ich die Lust verloren , mich weiter mit dem Thema zu beschäftigen.
Das kenne ich …
Ich stelle mir das so vor, dass der Automat, wenn er eine
Bedingung als gegeben erkannt hat (z.B. eine schließende zur
öffnenden Klammer gefunden hat), das, was darin als Argument
enthalten ist, an die nächst höhere Ebene der Verarbeitung
weitergibt. Ohje, das klingt doof.Das klingt nicht doof, das ist Rekursion. Wenn man Rekursion verwendet kann man sogar auf einen Stack verzichten.
Rekursion, stimmt. Aber wenn man am Ende auf den Stack verzichtet, ist es kein Kellerautomat mehr, oder?
Ich finde, das ist hier ganz gut beschrieben: http://compilers.iecc.com/crenshaw/ (Im wesentlichen in dem Kapitel über Interpreter).
Danke für den Link, aber was MICH betrifft … werde ich mich da jetzt wohl nicht durcharbeiten. Die Zeit der Klausuren liegt ein paar Jahre zurück, und momentan liegen keine entsprechenden Aufgaben vor mir
Grüße,
Moritz
Dito,
Kristian
hi,
also ich hab die Frage hier nochmal gestellt, weil mir in dem anderen Forum niemand helfen konnte. Hier sieht das ganz anders aus, Danke nochmal dafür.
Nun zum Thema… Ich will das nicht rekursiv lösen, sondern es sollte schon mit Stack sein. Nur weiss ich nicht wie ich da das ergebnis rauskriege. Hab mir auch überlegt, dass ich den Stack irgendwie so umstelle, dass ich es mit der umgekehrten polnischen Notation lösen kann, aber ich weiss nicht, ob das der richtige weg ist. Ich hab halt überhaupt keinen Plan wie ich die Aufgabe angehen soll, desswegen ist die Frage noch ziemlich allgemein gehalten.
Also falls jemand noch andere Anregungen hat oder interessante Seiten dann immer her damit.
Hallo,
also ich hab die Frage hier nochmal gestellt, weil mir in dem
anderen Forum niemand helfen konnte. Hier sieht das ganz
anders aus, Danke nochmal dafür.
http://forum.fachinformatiker.de/algorithmik/104219-…
Ich würde das anders formulieren: Auf eine Rückfrage hast du erst heute geantwortet…
Nun zum Thema… Ich will das nicht rekursiv lösen, sondern es
sollte schon mit Stack sein. Nur weiss ich nicht wie ich da
das ergebnis rauskriege. Hab mir auch überlegt, dass ich den
Stack irgendwie so umstelle, dass ich es mit der umgekehrten
polnischen Notation lösen kann, aber ich weiss nicht, ob das
der richtige weg ist. Ich hab halt überhaupt keinen Plan wie
ich die Aufgabe angehen soll, desswegen ist die Frage noch
ziemlich allgemein gehalten.
Das Umstellen ist schon mal eine gute Idee, denke ich.
Du kannst dir überlegen, wie man allgemein Ausdrücke von Infix- in Postfixnotation umwandelt, vermutlich brauchst du einen Keller/Stack, um die Operatoren zwischenzuspeichern.
Wenn man sich z.B. nur ‚+‘ und Klammern anschaut, wird aus
a + b
dann
a b +
und wenn b ein komplexerer Ausdruck ist, z.b.
a + (c Op d)
dann musst du
Wenn du das hast, kannst du dir noch überlegen, wie du die Punkt-vor-Strich-Regeln implementierst.
Grüße,
Moritz