Parser für logische Ausdrücke

Status
Nicht offen für weitere Antworten.

banshee

Bekanntes Mitglied
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.
 

diggaa1984

Top Contributor
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

Top Contributor
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

Bekanntes Mitglied
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?
 
S

SlaterB

Gast
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
 

banshee

Bekanntes Mitglied
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

Top Contributor
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]
 
Zuletzt bearbeitet:
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
L Methoden Parser für gängige Datumsformate? Allgemeine Java-Themen 1
L Generator für einen Parser implementieren Allgemeine Java-Themen 13
A Konstrukt ohne Main für Xml-Parser Allgemeine Java-Themen 1
F Parser Framework/Plugin für Datei in Custom-Format Allgemeine Java-Themen 2
J Best Practice Parser für Taschenrechner Allgemeine Java-Themen 4
P RegEx mit HTML Parser für Java möglich? Allgemeine Java-Themen 10
S HTML => DOM - Welcher Parser für meine Zwecke? Allgemeine Java-Themen 3
D Parser-generator für mathematische Funktionen Allgemeine Java-Themen 12
T Parser für BBCode? Allgemeine Java-Themen 3
A Parser für \ Allgemeine Java-Themen 12
W CSV-Parser Allgemeine Java-Themen 1
I DOM-Parser - Element im Element an bestimmten Stellen auslesen Allgemeine Java-Themen 1
B StAX Parser - mehrere Methoden, ein XML Allgemeine Java-Themen 4
offi EDIFACT Parser Allgemeine Java-Themen 7
Neumi5694 Parser - Zerlegen verschachtelter Funktionen Allgemeine Java-Themen 2
RalleYTN Lua Parser? Allgemeine Java-Themen 2
O Sax-Parser ließt XML-File doppelt Allgemeine Java-Themen 1
Thallius Simple JSON Parser Error null Allgemeine Java-Themen 6
H Best Practice Ideensuche: Flexibel hinzufügbare eigene Parser Allgemeine Java-Themen 6
V String nicht im String literal pool speichern - Parser Allgemeine Java-Themen 30
A Parser verursacht Speicherprobleme auf Server Allgemeine Java-Themen 2
H Kleiner HTML Parser (Facharbeit) Allgemeine Java-Themen 11
G REST Client / URL Parser Allgemeine Java-Themen 2
F ical4j Parser Allgemeine Java-Themen 7
M String tokenizer / parser Allgemeine Java-Themen 3
M Übergabe mehrer Files an selbstprogrammieren Parser Allgemeine Java-Themen 4
Landei Design-Problem Formel-Parser Allgemeine Java-Themen 10
E Parser basteln mit CUP Allgemeine Java-Themen 6
T HTML Parser Allgemeine Java-Themen 7
R Script parser Allgemeine Java-Themen 6
T Mathematik Parser Library? Allgemeine Java-Themen 4
N DOM Parser Allgemeine Java-Themen 2
J Parser / Scanner / Tokenizer gesucht Allgemeine Java-Themen 3
S Textfeld Parser sinnvoll? Allgemeine Java-Themen 3
D CSV Parser Allgemeine Java-Themen 12
T Webseite (HTML) Parser gesucht Allgemeine Java-Themen 8
R Parser: Datei auslesen, Datei erstellen - Geschwindigkeit Allgemeine Java-Themen 16
S html parser Allgemeine Java-Themen 3
G Parser erstellen Allgemeine Java-Themen 12
T Suche BBCode-Parser in Java Allgemeine Java-Themen 2
J Java Parser Tool verfügbar? Allgemeine Java-Themen 3
A api latex bzw. latex parser Allgemeine Java-Themen 2
B tipps zum schreiben eines mathematischen parser Allgemeine Java-Themen 13
Karl_Der_Nette_Anfänger Hat wer ne Lösung für verknüpfte Postleitzahlen? (Baum/Wurzel Struktur) Allgemeine Java-Themen 11
R 11 GB File lesen ohne zu extrahieren Filedaten Bereich für Bereich adressieren dann mit Multi-Thread id die DB importieren Allgemeine Java-Themen 3
G KeyListener für JTextField Allgemeine Java-Themen 5
webracer999 Library für Textsuche (z. B. include/exclude, and/or)? Allgemeine Java-Themen 5
I Module-Info für Jar erzeugen Allgemeine Java-Themen 7
krgewb Java-Bibliothek für ONVIF Allgemeine Java-Themen 1
B Simpler Eventlistener für Tastaturtaste bauen? Allgemeine Java-Themen 13
_user_q Eingegebenen Text Zeile für Zeile ausgeben lassen Allgemeine Java-Themen 11
E Key für TOTP Algorythmus(Google Authentificator) Allgemeine Java-Themen 0
S Formel für Sonnenwinkel in ein Programm überführen Allgemeine Java-Themen 11
M pfx-Zertifikat in Tomcat für SSL-Verschlüsselung nutzen Allgemeine Java-Themen 14
R Best Practice Erfahrungswerte für eine Migration von JSF nach Angular (oder anderes JS-Framework) Allgemeine Java-Themen 1
B HeapSort für Array of Strings funktioniert nur teilweise Allgemeine Java-Themen 3
jhCDtGVjcZGcfzug Klassen Was genau passiert hier? Kann mir das jemand bitte Zeile für Zeile erklären? Allgemeine Java-Themen 1
rosima26 Bester Sortieralgorithmus für kurze Arrays Allgemeine Java-Themen 40
S Mit Methoden kann man definieren für was <T> steht. Geht das auch irgendwie für Variablen? Allgemeine Java-Themen 12
MangoTango Operatoren while-Schleife für Potenz Allgemeine Java-Themen 3
B Lottospiel, genug Reihen tippen für 3 Richtige (Spaß mit Arrays)? Allgemeine Java-Themen 46
B Mit welchen Datentypen und Strukturierung am Besten dutzende Baccaratspiele Shcritt für Schritt durchsimulieren? Allgemeine Java-Themen 26
D Klassendesign für einen Pascal Interpreter Allgemeine Java-Themen 6
I OCR Library für Belegerkennung Allgemeine Java-Themen 7
farah GetterMathod für Farbkanäle Allgemeine Java-Themen 6
B Welcher Datentyp für sehr große Zahlenbereiche? Allgemeine Java-Themen 1
S Webservices für binäre Daten? Allgemeine Java-Themen 5
G Licence-Header für InHouse entwickelten Source Allgemeine Java-Themen 8
M Schleife für einen TicTacToe Computer Allgemeine Java-Themen 5
O git ignore für Intellji braucht es die .idea Dateien? Allgemeine Java-Themen 8
F Java Script für das Vorhaben das richtige? Allgemeine Java-Themen 9
M wiviel Java muss ich für die Berufswelt können ? Allgemeine Java-Themen 5
Robertop Datumsformat für GB ab Java 16 Allgemeine Java-Themen 1
Thallius Verschiedene entities für gleichen Code…. Allgemeine Java-Themen 8
OnDemand Zentrale "Drehscheibe" für verschiedene APIs Allgemeine Java-Themen 14
S Übergabe eines Sortierkriteriums für ein Artikel Array mittels BiPredicate<Artikel, Artikel> Allgemeine Java-Themen 13
F Streams als Alternative für dieses Problem ? Allgemeine Java-Themen 15
D SHA-3 für Java-version 1.8 Allgemeine Java-Themen 1
N Validator für einen SQL-Befehl Allgemeine Java-Themen 22
Muatasem Hammud Erstellung von Testdaten für Arrays Allgemeine Java-Themen 6
B Logikfehlersuche, das perfekte Lottosystem für 3 Richtige mit Arraylists? Allgemeine Java-Themen 61
G Methoden für die Zukunft sinnvoll? Allgemeine Java-Themen 4
M API für PLZ Umkreissuche Allgemeine Java-Themen 3
1Spinne JDK 8 für Eclipse installieren Allgemeine Java-Themen 5
Tobero Meine Funktion für das beinhalten eines Punktes in einem Kreis funktioniert nicht Allgemeine Java-Themen 5
H Interface PluginSystem ClassNotFound exception für library Klassen Allgemeine Java-Themen 10
N relativier Pfad für sqlite-Datenbank in Gradle/IntelliJ Allgemeine Java-Themen 2
buchfrau Anagram für beliebiges Wort Allgemeine Java-Themen 2
TonioTec Api für Datenaustausch zwischen Client und Server Allgemeine Java-Themen 0
W Suche Ursache für NPE - woher kommt sie? (Hilfe beim Debugging) Allgemeine Java-Themen 19
Kirby.exe Distanz Map für die Distanztransformation erstellen Allgemeine Java-Themen 1
F PI Regler für Heizung Allgemeine Java-Themen 7
8u3631984 Generelle Log4j.xml für alle Module Allgemeine Java-Themen 5
M Wie übergebe ich den Zähler für die Anzahl Rekursionsschritte korrekt? Allgemeine Java-Themen 2
B Login für User, der im Hintergrund Schedules ausführt Allgemeine Java-Themen 16
L RegEx für Teile einer Berechnung Allgemeine Java-Themen 14
S Java-Task-Management-Tool für Windows und Mac selber programmieren Allgemeine Java-Themen 4
M Java 2D Array für ein Grid erstellen ? Allgemeine Java-Themen 2
Z Welches GUI Framework für Java ist aktuell? Allgemeine Java-Themen 16
N Convert.FromBase64 von C# für Java Allgemeine Java-Themen 11

Ähnliche Java Themen

Neue Themen


Oben