# Parser für logische Ausdrücke



## banshee (30. Jul 2009)

Hallo,

ich müsste in meinem Programm einen Filter, der so aussehen könnte verarbeiten: NOT((A | B) & (C | NOT(D)))
D.h. ich muss den Ausdruck parsen und gleichzeitig ein Objekt daraus aufbauen. Kennt da jemand evtl. eine Bibliothek oder Material zum Nachlesen? Alles was ich gefunden habe, geht irgendwie in eine andere Richtung.


----------



## peetpan (30. Jul 2009)

ich habe fuer soetwas aehnliches mal javacc benutzt. hat gut funktioniert. https://javacc.dev.java.net/

ist vielleicht fuer so ein kleines parser-problem ein wenig holzhammer, aber man hat dann die moeglichkeit es sauber weiter auszubauen.

lg


----------



## andre111 (30. Jul 2009)

Hi,

schau dir das mal an:
http://www.java-forum.org/java-faq-beitraege/12306-parser-fuer-mathematische-formeln.html
Ist zwar für mathematische und nicht für logische Ausdrücke, sollte aber das Grundprinzip erklären.

Gruß Andre


----------



## diggaa1984 (30. Jul 2009)

ich hatte da mal was im 1. semester gebaut .. baum aufgebaut, optimiert, ausgewertet .. lief super für nen baum mit >80 knoten, sogar extra schreibtischtest gemacht, alles korrekt .. aber ein NOT true konnte er nicht sauber auflösen und is abgeschmiert ^^ .. bitter .. also nich ganz brauchbar sonst hättst da was haben können


----------



## Landei (30. Jul 2009)

Ich denke, der Shunting Yard Algorithmus funktionert hier auch. Dadurch würdest du eine (klammerfreie) Postfix-Notation bekommen, also NOT((A | B) & (C | NOT(D))) --> A B | C D NOT | & NOT. Damit lässt sich dann ziemlich stressfrei ein Baum aufbauen usw.


----------



## banshee (31. Jul 2009)

Also so auf Anhieb gefällt mir eignetlich der mathematische Parser am besten. Den müsste man nur noch leicht umbauen und schon sollte das klappen. Das NOT ist dann ja einfach eine weitere Fallunterscheidung, nur wie man die Objekte weiterverarbeitet, weiß ich jetzt nicht. Wenn ich da (3+4) verarbeite, wird stattdessen ja einfach 7 eingefügt. In meiner Anwendung käme da ein Objekt raus und was mache ich damit? Trage ich da dann einfach einen Platzhalter in den Ausdruck ein, damit ich weiß, welches Objekt gemeint ist?


----------



## SlaterB (31. Jul 2009)

ein Problem ist noch, dass nun Variablen und Funktionen vermischt sind,
wenn du ein N einliest, kannst du nicht direkt wissen, ob es zu einem NOT gehört oder eine Variable N darstellt,
etwas leichter wirds, wenn Variablen grundsätzlich nur einen Buchstaben lang sind und Funktionen länger,
oder Funktionen gar keine Buchstabenverwenden, ! statt NOT,
du könnstest auch NOT normale einlesen und einmal zu Beginn im String NOT durch ! ersetzen

jedenfalls brauchst du für Variablen auch einen neuen Knoten-Typ, und die Information, welchen Namen die Variable hat, muss natürlich darein,
später ein neuer Verarbeitungsschritt: die Belegung aller Variablen mit einem Wert

die Berechnung kannst du von double auf boolean umstellen oder 1 = true/ 0 = false verwenden


----------



## matches (2. Aug 2009)

Hi,

du kannst auch jEval (JEval) verwenden. Ich fands damals, als ichs mal verwendet hab, ganz brauchbar


----------



## banshee (6. Aug 2009)

Mal eine ganz dumme Frage, aber wie importiere ich eigentlich so ein Paket wie jeval möglichst unkompliziert in eclipse? Ich wurschtel mir da immer sonst einen zurecht und ich habe die dunkle Vorahnung, dass das irgendwie ganz leicht über import as existing project oder ähnliches geht. Aber was ich auch versuche, die sources landen nie im richtigen Ordner und irgendwann fang ich dann wieder an hin- und herzuschieben usw.


----------



## DrZoidberg (7. Aug 2009)

Ich hab mal eines meiner alten Programme genommen und an dein Problem angepasst.
Es ist ein relativ kompakter Parser, enthält aber keine Syntaxprüfung.
Du kannst dort z.B. sowas eingeben
"a&b|a&c"
oder "not(a&b | c&d)"
Der Parser versteht not, & und | und kann beliebig viele Klammern verarbeiten.
& hat übrigens eine höhere Priorität als |.
Der Parser verwendet aber keine Rekursion, sondern benutzt einen Stack um den Ausdruck in eine Postfix Form umzustellen. In dieser Form lässt er sich dann sehr leicht auswerten.


[Java]
import java.util.ArrayList;
import java.util.Stack;

public class Parser {

    static ArrayList<Operator> operators=new ArrayList<Operator>();
    static {
        operators.add(new Operator("NOT", 1, 3) {
            boolean calculate(boolean[] operands) {
                return !operands[0];
            }
        });
        operators.add(new Operator("&", 2, 2) {
            boolean calculate(boolean[] operands) {
                return operands[0] && operands[1];
            }
        });
        operators.add(new Operator("|", 2, 1) {
            boolean calculate(boolean[] operands) {
                return operands[0] || operands[1];
            }
        });
    }


    public static void main(String[] args) {
        System.out.print("Bitte logischen Ausdruck eingeben: ");
        String input=System.console().readLine();
        ArrayList<Object> expr=tokenize(input);

        expr=convertToPostOrder(expr);
        System.out.println("Postfix Notation: "+expr);

        boolean result=eval(expr);
        System.out.println("Ergebnis = "+result);
    }


    static ArrayList<Object> tokenize(String str) {

        ArrayList<Object> output=new ArrayList<Object>();

        for(int i=0; i<str.length(); i++) {
            char c=str.charAt(i);

            if(Character.isWhitespace(c)) continue;
            int end=i+1;
            if(Character.isLetter(c)) {
                while(end < str.length() && Character.isLetter(str.charAt(end))) {
                    end++;
                }
            }
            String word=str.substring(i, end);
            int index=-1;
            for(Operator op: operators) {
                if(op.equals(word)) index=operators.indexOf(op);
            }
            if(index >= 0) {
                output.add(operators.get(index));
            } else {
                output.add(word);
            }
            i=end-1;
        }
        return output;
    }


    static ArrayList<Object> convertToPostOrder(ArrayList<Object> expr) {
        ArrayList<Object> output=new ArrayList<Object>();
        Stack<Object> stack=new Stack<Object>();

        for(Object o: expr) {
            if(o instanceof String) {
                if(o.equals("(")) stack.push(o);
                else if(o.equals(")")) {
                    while(true) {
                        Object o2=stack.pop();
                        if(o2.equals("(")) break;
                        output.add(o2); 
                    }
                } else output.add(o);
            }
            else if(o instanceof Operator) {
                Operator op=(Operator)o;
                while(!stack.empty()) {
                    Object o2=stack.pop();
                    if(o2.equals("(") || ((Operator)o2).getPriority()<op.getPriority()) {
                        stack.push(o2);
                        break;
                    }
                    output.add(o2);
                }
                stack.push(o);
            } else throw new RuntimeException("Error");
        }
        while(!stack.empty()) {
            output.add(stack.pop()); 
        }
        return output;
    }


    static boolean eval(ArrayList<Object> expr) {
        for(int i=0; i<expr.size(); i++) {
            if(expr.get(i) instanceof String) {
                String variable=(String)expr.get(i);
                System.out.println("Bitte Wert fuer Variable "+variable+" eingeben: ");
                boolean value=Boolean.parseBoolean(System.console().readLine());
                for(int j=i; j<expr.size(); j++) {
                    if(expr.get(j).equals(variable)) {
                        expr.set(j, value);
                    }
                }
            }
        }
        Stack<Boolean> stack=new Stack<Boolean>();
        for(Object o: expr) {
            if(o instanceof Boolean) stack.push((Boolean)o);
            else {
                Operator op=(Operator)o;
                int nrOp=op.numberOfOperands();
                boolean[] operands=new boolean[nrOp];
                for(int i=0; i<nrOp; i++) {
                    operands[nrOp-i-1]=stack.pop();
                }
                stack.push(op.calculate(operands));
            }
        }
        return stack.pop();
    }
}


abstract class Operator {

    private final String op;
    private final int priority;
    private final int numberOfOperands;

    Operator(String op, int numberOfOperands, int priority) {
        this.op=op;
        this.priority=priority;
        this.numberOfOperands=numberOfOperands;
    }

    int getPriority() {
        return priority;
    }

    int numberOfOperands() {
        return numberOfOperands;
    }

    abstract boolean calculate(boolean[] operands);

    public String toString() {
        return op;
    }

    public boolean equals(Object o) {
        if(o instanceof String) return ((String)o).equalsIgnoreCase(op);
        else if(o instanceof Character) return op.length()==1 && op.charAt(0)==((Character)o).charValue();
        else return this == o;
    }
}
[/Java]


----------

