Java SAT (Haltbarkeitsproblem) mit Regex

S

slitec

Mitglied
Hallo,
ich bin gerade dabei ein Programm zu schreiben, welches das Erfüllbarkeitsproblem löst (bzw. SAT = satisfiability problem). Hierzu darf die aussagenlogische Formal aus dem Alphabet: X,1,0,(,),V,&,- bestehen. Dabei steht das „V“ für Oder, das „&“ für UND und das „–„ für die Negation. Mit X,1,0 lassen sich somit auch alle Zahlen kodieren (z.B. die Zahl 1 = X01, 2= X02 usw.). Damit nur dieses Alphabet vorkommt, verwende ich das Pattern machting. Dies wird wie folgt geprüft:


Java:
public void suche(String eingabe) {
        
        if(Pattern.matches("[X10()V&-]+", eingabe) == true)
        {
            System.out.println("Eingabestring ist zulässig");
        }
        else
        {
            System.out.println("Eingabestring ist unzulässig");
        }



Nun habe ich einige Schwierigkeiten:
1)
Damit syntaktische Korrektheit garantiert wird, sollten die Konstellationen wie „ X1 V& X2“, „X1 VV X2“, „X1 && X2“ nicht zugelassen werden.
Frage: Gibt es eine Möglichkeit mit dem Pattern-Matching diese Konstellationen auszuschließen, sodass z.B. diese als „false“ angesehen werden und die Nachricht „Eingabestring ist unzulässig“ ausgegeben wird? Ich habe schon sehr viel im Internet dazu gesucht aber leider nichts gefunden.

2)
Nachdem ich die syntaktische Korrektheit erlangt habe, geht’s zum Auswerten. Kann mir da jemand vielleicht einen Tipp geben, wie ich am besten diese aussagenlogischen Ausdrücke auswerten kann? Auf dem Blattpapier würde ich hierzu eine Baumstruktur erstellen und mit der innersten Klammer anfangen. Wenn die Formel wie folgt aussieht :
(X10 V X01)-((X11 & X01) V X10))
3. 1. 2.
-- Dann würde ich zuerst 1. Auswerten, dann mit 2. Auswerten und anschließend das ganze mit 3. Auswerten.
Frage: Wie könnte ich das in Java umsetzen ? Hat da jemand ein Vorschlag für mich?

3)
Es gibt noch einen speziellen Fall, der ebenfalls direkt ausgeschlossen werden soll.
Wenn dieselbe Variable mit einem UND verknüpft wird, und eine davon negiert ist, dann soll ist dieser Bereich schon mal nicht erfüllbar. Dies sieht dann wie folgt aus:
(X1 & -X1) --> nicht erfüllbar.
Frage: Wie könnte ich dies mein Programm erkennen lassen? Es sollte hier also erkannt wird, dass dieselbe Variable (einmal z.B. X1 und einmal negiert X1) mit der Operation & verknüpft wurde?

Ich bedanke mich schon mal für die Tipps und Denkanstöße.
 
T

thecain

Top Contributor
mMn auf jeden Fall nicht mit Regex. Ich würde da Fall eine Art Parser verwenden. Dieser kann dann auch die Gültigkeit prüfen.
 
Zuletzt bearbeitet:
L

LimDul

Top Contributor
Ich sehe zwei Möglichkeiten:
a) Einen bestehenden Parser verwenden, für den man dann eine Grammatik definiert (z.B. eine Backus-Naur-Form: https://de.wikipedia.org/wiki/Backus-Naur-Form).
Vorteil: Man muss keinen Parser schreiben
Nachteil: Man muss die Grammatik definieren und nach dem Parsen mittels der Grammatik das noch seine eigene Datenstruktur bringen
b) Einen eigenen Parser
Vorteil: Man kann es direkt in seine eigene Datenstruktur bringen
Nachteil: Man muss den Parser schreiben

Ich würde zu b) tendieren - aber das erst mal hinten anstellen.

Ich würde das Pferd von der anderen Seite aufzäumen. Erstmal deine Datenstrukturen definieren, mit denen du auswerten willst. Und sobald du die hast, kannst du dir dann überlegen, wie du die Daten parst. Aber dann weißt du wo du hin willst - und kannst auch besser bewerten, welcher Ansatz passt.
 
S

slitec

Mitglied
Ok vielen
Ich sehe zwei Möglichkeiten:
a) Einen bestehenden Parser verwenden, für den man dann eine Grammatik definiert (z.B. eine Backus-Naur-Form: https://de.wikipedia.org/wiki/Backus-Naur-Form).
Vorteil: Man muss keinen Parser schreiben
Nachteil: Man muss die Grammatik definieren und nach dem Parsen mittels der Grammatik das noch seine eigene Datenstruktur bringen
b) Einen eigenen Parser
Vorteil: Man kann es direkt in seine eigene Datenstruktur bringen
Nachteil: Man muss den Parser schreiben

Ich würde zu b) tendieren - aber das erst mal hinten anstellen.

Ich würde das Pferd von der anderen Seite aufzäumen. Erstmal deine Datenstrukturen definieren, mit denen du auswerten willst. Und sobald du die hast, kannst du dir dann überlegen, wie du die Daten parst. Aber dann weißt du wo du hin willst - und kannst auch besser bewerten, welcher Ansatz passt.
Ok vielen Dank schon mal für die Antwort. Wenn ich die Grammatik definiert habe, wie könnte ich dann weiter machen? Ich müsste ja irgendwie zuerst an die innerste Klammer kommen und diese berechnen? Hättest du dafür vielleicht auch einen Ansatz?
 
B

Barista

Bekanntes Mitglied
Frage: Gibt es eine Möglichkeit mit dem Pattern-Matching diese Konstellationen auszuschließen, sodass z.B. diese als „false“ angesehen werden

Nein, reguläre Ausdrücke sind prinzipiell nicht zum Arbeiten auf rekursiven Strukturen geeignet.

Ich habe mal gelesen, dass es in Pearl Erweiterungen dazu gibt, habe aber keine konkrete Ahnung.

In einem Java-Magazin vor langer Zeit (2002 oder 2003) gab es mal einen Artikel über das Verfahren "rekursiver Abstieg".

Nach diesem Prinzip habe ich meine Parser geschrieben.

Wahrscheinlich findest Du im Netz auch was darüber.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
N Lottowebsite programmieren mittels Java, HTML,.... Allgemeine Java-Themen 1
O Input/Output java.io.File beenden Allgemeine Java-Themen 5
S Java class direved from inner class Allgemeine Java-Themen 6
O Leerzeichen und Umlaute im Pfad einer Java Applikation machen Probleme Allgemeine Java-Themen 13
Gaudimagspam CSV-Datei auslesen in Java Allgemeine Java-Themen 7
T Meine Frage lautet wie ich 2 CSV Dateien miteinander in Java verbinde und Spalten die zueinander gehören durch den gleichen Key zusammen ausgebe? Allgemeine Java-Themen 5
H Java SDK unter 32 Bit Allgemeine Java-Themen 5
P Unterschied Java SE und Java EE Allgemeine Java-Themen 2
B Methoden Java Getter und Setter Methoden Allgemeine Java-Themen 9
M Registry Autostart Eintrag mit Java erstellen (über Windows cmd) Allgemeine Java-Themen 7
M Registry Autostart Eintrag ertstellen mit Java (Runtime.getRuntime().exec()) Allgemeine Java-Themen 0
S Java-Task-Management-Tool für Windows und Mac selber programmieren Allgemeine Java-Themen 4
M java.util.prefs.Preferences "not visible" Allgemeine Java-Themen 7
M Website Quelltext mit Java einlesen Allgemeine Java-Themen 10
J Java Filechooser Speichern Allgemeine Java-Themen 8
Dann07 Java-Programm findet DLLs nicht! Allgemeine Java-Themen 20
F Fehlermeldung: java.lang.NoClassDefFoundError: org/apache/commons/net/ntp/NTPUDPClient Allgemeine Java-Themen 6
T Java-Anfänger möchte professionell coden lernen Allgemeine Java-Themen 23
M Java 2D Array für ein Grid erstellen ? Allgemeine Java-Themen 2
H Java Dom Childelemente von de Childelemente von den Childelement bekommen Allgemeine Java-Themen 1
P USER Management in SQL übergreifend auf JAVA Programm Allgemeine Java-Themen 41
platofan23 Wie .txtDatei im Java Eclipse-Projekt bzw. in der Jar speichern? Allgemeine Java-Themen 7
Z Welches GUI Framework für Java ist aktuell? Allgemeine Java-Themen 16
I Java und XML Allgemeine Java-Themen 10
K Java Programmfluss Allgemeine Java-Themen 13
R Delete files before creating new from temp using Java file method Allgemeine Java-Themen 1
N Byte Array in Java "dekomprimieren" Allgemeine Java-Themen 3
N Convert.FromBase64 von C# für Java Allgemeine Java-Themen 11
C Java RMI Client - Server Allgemeine Java-Themen 0
Ullenboom Ein neues Java-Buch entsteht, willst du helfen? Allgemeine Java-Themen 7
N fixed-keyword von C# für Java Allgemeine Java-Themen 6
G Java Reflections Allgemeine Java-Themen 6
bueseb84 Java : Cannot find Symbol Allgemeine Java-Themen 7
N E-Mail per Java verschicken Allgemeine Java-Themen 2
Y Java Bruttoberechnen + runden Methode Allgemeine Java-Themen 1
Y Java Methoden unterschiedliche Zahlenreihen Allgemeine Java-Themen 2
M java.io.EOFException bei einem DataoutputStream ?! Allgemeine Java-Themen 2
D Java Kuriositäten / Rätsel Allgemeine Java-Themen 9
S File lesen und schreiben Java 6 Allgemeine Java-Themen 2
1 Java Scanner Allgemeine Java-Themen 2
J Key Keystore Certificate Java Android Development Allgemeine Java-Themen 1
J Java KeyStore Schlüssel Allgemeine Java-Themen 10
F Sich automatisch aufrufende Java-Methoden Allgemeine Java-Themen 2
M Java model class ? Allgemeine Java-Themen 9
C Java Script Pause berechnen Allgemeine Java-Themen 5
P Input/Output entfernte Datei mit Java öffnen ohne Download Allgemeine Java-Themen 5
M Java komplexe Map mit 2 values ? Allgemeine Java-Themen 8
bueseb84 Java Deploy to JFrog Repository Allgemeine Java-Themen 3
R Java mit Selenium "Geister"Loop Allgemeine Java-Themen 1
M SQL-Developer Installation: Unable to launch the Java Virtual Machine Located at path msvcr100.dll Allgemeine Java-Themen 1
L Java frage Allgemeine Java-Themen 3
D Verkauf von einem Programm welches ich in Java geschrieben habe Allgemeine Java-Themen 4
M this application requires a java runtime environment 1.8.0 Allgemeine Java-Themen 2
W Haben Konstruktoren in Java eigentlich immer mindestens einen Parameter? Allgemeine Java-Themen 4
N Kurs Java Oraclce Certified Allgemeine Java-Themen 0
C Java und die IDE´s und die Zukunft Allgemeine Java-Themen 11
M Java – Warum kann ich plötzlich bei Android Studio Grafische Benutzeroberflächen mit der Maus gestalten? Allgemeine Java-Themen 5
M JAVA API in Eclipse auf deutsch Allgemeine Java-Themen 18
hello_autumn Java_Home geändert auf Java 13, trotzdem wird Java Version 8 angezeigt. Allgemeine Java-Themen 2
S Java.exe exestiert, aber irgendwie auch nicht Allgemeine Java-Themen 11
J CMD Befehl in Java Consolenprogramm ausführen Allgemeine Java-Themen 6
Bluedaishi Java versteckte Partition Allgemeine Java-Themen 9
O Java-Applikation tut in Netbeans, als JAR nicht, wegen Pfadangaben einer benötigten Datei Allgemeine Java-Themen 8
M Hilfe bei einer Java Programmieraufgabe! Ab morgen Montag um 08:00 Uhr Allgemeine Java-Themen 5
W Java Telegram Bot - Eingabe durch User Allgemeine Java-Themen 2
A Java-Webanwendung Allgemeine Java-Themen 7
Tashtego Externe Java Klasen zur Laufzeit einbinden Allgemeine Java-Themen 10
K Binärbäume in Java Allgemeine Java-Themen 2
P Swing Exception in thread "AWT-EventQueue-0" java.lang.IndexOutOfBoundsException: npoints > xpoints.length || npoints > ypoints.length Allgemeine Java-Themen 5
M Java 8 nach Java 6 konvertieren Allgemeine Java-Themen 7
S Java verknüpft mit Aseba Allgemeine Java-Themen 0
Tashtego Java 8 Security Update Allgemeine Java-Themen 3
U Klassen Komplexe Datenstruktur in Java Allgemeine Java-Themen 4
B Java Mail: Prüfung auf neue Emails Allgemeine Java-Themen 1
B Java Mail: Emails sortieren? Allgemeine Java-Themen 5
B Java Mail: Prüfen, ob Email hat ein Anhang oder nicht Allgemeine Java-Themen 2
T Java-Quiz Code Fehler Allgemeine Java-Themen 10
X Collections Gibt es eine Klasse welche die Vorteile von List und HashMap vereint, aber konstante Laufzeit (O(1)) hat in Java? Allgemeine Java-Themen 4
L Python in Java ausführen Allgemeine Java-Themen 4
L Nach dem Login // Java Desktop Software Allgemeine Java-Themen 7
V Maus mitthilfe Bewegungssensor steuern (Java) Allgemeine Java-Themen 12
L Eclipse Java Code ausführen Allgemeine Java-Themen 18
D Was sind Bibliotheken in Java/Pyhton? Allgemeine Java-Themen 1
L Echtzeitdaten aus einer Webseite ziehen mit Java Allgemeine Java-Themen 19
F Java Code ausführen direkt nach Anmelden in Windows Allgemeine Java-Themen 2
F Java Web App - welche Technologien? Allgemeine Java-Themen 11
B Java Mail: Unterscheidung bei Attachments und eingefügte Bilder in Email Allgemeine Java-Themen 18
S Java Zugriff auf Netzwerklaufwerk Allgemeine Java-Themen 1
M Rectangle mit Java erstellen? Allgemeine Java-Themen 9
Tommy135 Input/Output Application aus Java package starten Allgemeine Java-Themen 2
J Jasper Reports - Compilerproblem nach Umstellung von Groovy auf Java Allgemeine Java-Themen 7
I Java mit Board of Symbols Allgemeine Java-Themen 4
S Java Installation Fehlercode 1603 Allgemeine Java-Themen 9
J Arduino – Processing – Java Allgemeine Java-Themen 0
D [Minecraft] Java Start Fehler (Core-Dump) Allgemeine Java-Themen 1
T Wert an laufenden Java-Prozess übergeben Allgemeine Java-Themen 10
J Problem beim Umstellen auf Java jdk 13 Allgemeine Java-Themen 3
J Problem bei Install java 13 Allgemeine Java-Themen 3
J Erste Schritte Java 8 Tutorials trotz Java 13 Allgemeine Java-Themen 22
E Listen in Java aneinanderfügen, subtrahieeren usw. Allgemeine Java-Themen 14

Ähnliche Java Themen

Anzeige

Neue Themen


Oben