Algorithmus zum Auswerten eines logischen Ausdrucks gesucht
Robert Bude
Ich schreibe an einem Programm in C und muss nun einen logischen Ausdruck
der Form "(a & b) || c" welcher mir als String gegeben ist auswerten. Dieser
String kann natürlich noch weitaus komplizierter werden.
Ich suche nun nach einem Algorithmus wie ich diesen mir auswerten kann. Was
ich bis jetzt gefunden habe, ist den ausdruck in einem Baum abzulegen.
Leider stand nie dazu wie. Ich möchte das ganze auch selbst umsetzen mir
reicht also wirklich der algorithmus.
Vereinfachung: es kommt nur (,),&,|| vor ;) und bezeichner (also
variablennamen)
So weit den String in seine einzelnen Token zu zerlegen bin ich schon. nun
muss ich die nur noch irgendwie innen baum einsortieren und dann diesen
berechnen lassen. vielleicht kann mir jemand weiterhelfen. Find so richtig
was treffendes auch nach stundenlangen suchen im netz nicht ;(
Danke
Robert Bude
Daniel Hohenberger
> So weit den String in seine einzelnen Token zu zerlegen bin ich schon. nun
> muss ich die nur noch irgendwie innen baum einsortieren und dann diesen
> berechnen lassen. vielleicht kann mir jemand weiterhelfen. Find so richtig
> was treffendes auch nach stundenlangen suchen im netz nicht ;(
>
Ich denke ein Parser-Generator wie YACC und einen Scanner-Generator wie
(F)Lex sollte dir weiterhelfen können. Diesem wirft man eine Grammatik
vor, die die zu erkennende Sprache (in deinem Fall die einfachen
Ausdrücke) beschreibt, und er generiert daraus einen Parser, der das
ganze in eine Baumstruktur einliest. Ich kenne mich zwar nur mit den
Java-Tools CUP und JFlex aus, das dürfte aber vom Resultat her kein
großer Unterschied ausmachen.
MfG,
Daniel
P.S.: Für dein Problem ist das zwar möglicherweise wie mit Kanonen auf
Spatzen geschossen, aber es geht einfach und du erfindest nicht das Rad
neu. Ansonsten kannst du auch versuchen, Klammerungen u.s.w. zu erkennen
und damit den Baum zu konstruieren.
--
my homepage : http://hd42.de
'Life is wasted on the living' - Zaphod Beeblebrox the Fourth
Christian Kortes
> Ich schreibe an einem Programm in C und muss nun einen logischen Ausdruck
> der Form "(a & b) || c" welcher mir als String gegeben ist auswerten. Dieser
> String kann natürlich noch weitaus komplizierter werden.
> Ich suche nun nach einem Algorithmus wie ich diesen mir auswerten kann. Was
> ich bis jetzt gefunden habe, ist den ausdruck in einem Baum abzulegen.
> Leider stand nie dazu wie. Ich möchte das ganze auch selbst umsetzen mir
> reicht also wirklich der algorithmus.
Google mal nach "recursive descent".
MfG,
Christian
Tillmann Rendel
> So weit den String in seine einzelnen Token zu zerlegen bin ich schon.
> nun muss ich die nur noch irgendwie innen baum einsortieren und dann
> diesen berechnen lassen.
Zum Parsen: Stichwort "rekursiver Abstieg".
Zum Auswerten: Tiefensuche, dabei die (Zwischen-)ergebnisse nach "oben"
weitergeben.
Da es beim Parsen "runter" und beim Auswerten "hoch" geht, kannst Du Dir
sogar das explizite Erstellen des Baumes sparen, und die Ausdrücke beim
parsen direkt auswerten.
Viel Erfolg,
Tillmann
Volker Birk
> Ich schreibe an einem Programm in C und muss nun einen logischen Ausdruck
> der Form "(a & b) || c" welcher mir als String gegeben ist auswerten. Dieser
> String kann natürlich noch weitaus komplizierter werden.
Steht da a, b und c drin, oder sind's nur Literale? Falls nur Literale,
nimm den Baum oder eine Stackmachine (dreh die Infixe in Präfixe um und
mach's wie Postscript). Falls Bezeichner drin vorkommen: definiere zuerst
mal die Sprache.
VB.
--
X-Pie Software GmbH
Postfach 1540, 88334 Bad Waldsee
Phone +49-7524-996806 Fax +49-7524-996807
mailto:v...@x-pie.de http://www.x-pie.de
Kai Rohrbacher
Daniel Hohenberger (nag...@hd42.de) wrote about "Re: Algorithmus zum Auswerten eines logischen Ausdrucks gesucht":
> P.S.: Für dein Problem ist das zwar möglicherweise wie mit Kanonen auf
> Spatzen geschossen, aber es geht einfach und du erfindest nicht das Rad
> neu. Ansonsten kannst du auch versuchen, Klammerungen u.s.w. zu erkennen
> und damit den Baum zu konstruieren.
Er braucht den Baum doch gar nicht, eine einfache Stack-Maschine mit 2
Stacks sollte auch reichen: Er parst seine Tokens von links nach rechts
durch, schiebt seine Variablen auf den einen Stack und seine noch nicht
abgearbeiteten Operatoren auf einen zweiten.
-Den zugehörigen Pseudo-Code (uralt..) habe ich gerade nicht zur Hand,
kann ich aber bei Bedarf raussuchen.
Kai
Kai Rohrbacher
Robert Bude (hann...@rupat.de) wrote about "Algorithmus zum Auswerten eines logischen Ausdrucks gesucht":
hier der versprochene uralt-Algorithmus einer kleinen Stack-Maschine, die
Dein Problem löst.
Der Algorithmus klingt zunächst kompliztiert, aber wenn man mal das
Beispiel durchgemacht hat, sieht man, dass er in Wirklichkeit total simpel
ist: Der erste Teil des Algorithmus wandelt den infix-Ausdruck in postfix-
Notation. Der kann danach sehr simpel ausgewertet werden.
Die Infix->Postfix-Notation ist dabei echt elegant: Der w-Stack sammelt
sozusagen einfach die niedrig-prioren Operatoren (und Operanden), indem er
die Ausführung solange "auf die lange Bank (bzw. eben: Stack)" schiebt,
wie es geht. Trifft es dann aber bei der Abarbeitung im String auf einen
Operator mit einer Priorität kleinergleich derjenigen auf der aktuellen w-
Stackspitze, dann weiß es, dass nun eine Ausdrucksberechnung erfolgen muss
-und verschiebt deshalb all die vorrangigen (und gleichrangigen)
Operatoren in den Postfix-Stack. Im Endeffekt war's das schon, es kommt
dann nur noch eine Regel dazu, um eine explizite Klammerung zu
berücksichtigen: Dazu wird einfach jede öffnende Klammer quasi als
"guardian" mit auf den w-Stack geschoben. Taucht dann in der weiteren
Abarbeitung eine zugehörige schließende Klammer auf, so müssen natürlich
alle aufgestauten Operatoren bis zu jener zugehörigen öffnenden Klammer
auf den Postfix-Stack geschoben werden.
Vielleicht noch zwei kleine Anmerkungen dazu: Der Ausdruck muss geklammert
sein, d.h.: Zur Not einfach ein Klammernpaar außen herum setzen (schadet
ja eh nicht). Zum anderen müssen Deine Operator-Tokens zwischen monadisch
und binär unterscheiden (klassisches Problem: steht das Minuszeichen nun
für den binären Operator "a-b" oder für das monadische "-a"?). Aber wenn
Du wie Du sagst schon alles in Token-Darstellung hast, sollte das eh kein
Problem mehr sein.
Initially, both stacks are empty. Then the following rules are applied:
1) scan the formula's elements from the left to right; if the current
element is an operand or a value, push it onto the p-stack
2) if it is an operator then look up its precdence p1; start to pop
operators from the w-stack and push them onto the p-stack as long as their
respective precedences q are >= p1; after this, push the operator itself
onto the w-stack
3) if it is a closing bracket ")", then start to pop operators from the w-
stack and push them onto the p-stack until an opening bracket "(" is found
and remove this "("-bracket
4) if it is an opening bracket "(", then push it onto the w-stack
5) repeat steps 1..4 until the input stream is empty; if an error occurs
in between, then the expression is not in proper infix notation
The p-stack afterwards has the sequence of operations required in postfix
notation.
Note however that the p-stack is now assumed to be "reversed", i.e.: The
first element to popped out is to be assumed the first pushed in! (This
assumes a data structure like a double ended queue or a simple sequence
"pop from stack1, push to stack2 until stack1 is empty, then use stack2
instead of stack1"). -This will become more clear in the example below.
Here is the processing sequence for the p-stack
1) pop top-level element: if it is a value / operand then push it onto the
w-stack
2) if it is an operator then look up the number of required arguments: pop
these from the w-stack and issue the respective operation, then push the
result back onto the w-stack (note the sequence matters: for example,
(3,5,minus) is processed into pop = 3, pop = 5, pop = minus and must
result into 3 minus 5 then)
3) repeat steps 1..2 until the p-stack is empty
4) if w-stack consists of only one value / operand AND p-stack is empty,
then return that value as result else error "invalid formula"
"processing" the operation is for the initial "unit-matching" phase only
to find out a result type, for example "(3,5,minus)" would have to be
processed as "<value>,<value>,"binary minus" which must result into
<value> (due to the sense "substracting to values from each other results
into a value once again").
In the second phase, the true calculation would have to take place -note
the distinction into two phases to avoid lengthy calculations which after
minutes or hours would result into an error message only.
Example of Algorithm
Let's assume that initial expression (3+5*7/(4+3)-1) here:
Element action w-stack p-stack
"(" put on w-stack (
3 put on p-stack ( 3
+ no other ops on w-stack -> on w-stack (+ 3
5 put on p-stack (+ 5
* no ops with prec. >= * on w-stack -> on w-stack (+* 5
7 on p-stack (+* 5 7
/ one op ("*") with prec. >= on w-stack -> rule 2 (+/ 3 5 7 *
( put on w-stack (+/( 3 5 7 *
4 put on p-stack (+/( 3 5 7 * 4
+ no ops with prec. >= + on w-stack -> on w-stack (+/(+ 3 5 7 * 4
3 put on p-stack (+/(+ 3 5 7 * 4
3
) pop&push up to next ")" (+/ 3 5 7 * 4
3 +
- two ops have prec. >= - -> rule 2 (- 3 5 7 * 4
3 + / +
1 put on p-stack (- 3 5 7 * 4
3 + / + 1
) rule 3 3 5 7 * 4
3 + / + 1 -
stack empty, finished!
Processing the p-stack sequence is easy:
Element action w-stack p-stack
3 put on w-stack 3 5 7 * 4 3 + / + 1
-
5 put on w-stack 3 5 7 * 4 3 + / + 1 -
7 put on w-stack 3 5 7 * 4 3 + / + 1 -
* p1=pop7, p2=pop5, push 5*7 to w-stack 3 35 4 3 + / + 1 -
4 push on w-stack 3 35 4 3 + / + 1 -
3 push on w-stack 3 35 4 3 + / + 1 -
+ p1=pop3, p2=pop4, push 3+4 to w-stack 3 35 7 / + 1 -
/ p1=pop7, p2=pop35, push 35/7 to w-stack 3 5 + 1 -
+ p1=pop5, p2=pop3, push 3+5 to w-stack 8 1 -
1 push on w-stack 8 1 -
- p1=pop1, p2=pop8, push 8-1 to w-stack 7
p-stack empty, w-stack has one element, finished
Gruß,
Kai Rohrbacher
Robert Bude
mittlerweile hinbekommen
(Überlegen und Kopf zerbrechen hat tatsächlich mal mehr gebracht als im Inet
rumzuwuseln)
;)