Divide-and-Conquer vollst.geklammert.Arithm.Ausd

Hallo wer-weiss-was community,
ich bastel garade an einer Problemlösng die mir noch nicht so ganz einleuchten will.

Ziel ist es mit devide and conquer einen vollständig geklammerten ausdruck zu berechnen der von einer datei als string eingelesen wird.

probleme habe ich bei dem D&C ansatz . Die frage ist also, wie arbeite ich mit den eingelesenen daten weiter?! ich hab keine ahnung wie ich da anfangen soll aufzuteilen, zu ersetzen und wieder zusammen zu fügen.

mein bisheriger code :

package AlgoLab2;

import java.io.*;
import java.util.*;

public class FileRead {

public static void main(String[] args) {

String a;
String line;
ArrayList string = new ArrayList();
split machmal = new split();

try {
FileReader fileInput = new FileReader(„U:\eclipse_workspace\Expression.txt“); // öffntet die gewünschte txt Datei

BufferedReader in = new BufferedReader(fileInput); // txt wird in den BufferReader geladen

for (int i = 0; (line = in.readLine()) != null; i++) { // durchlaufen,
// bis line
// =
// null(datei
// zu ende
// ist)
string.add(line); // array wird mit line (der aktuellen Zeile)
// belegt
}
} catch (IOException e) {
System.out.println(„IO-Fehler!“);
}

for (int i = 0; i

package AlgoLab2;

public class split {

public split() {

}

public String[] split(String b) {

String[] a;

a = b.split(" ");

return a;

}

}

ein bischen mehr Informationen solltest du schon geben. Es gibt mehre „Arten“ einen D&C Ansatz zu implementieren/programmieren.

siehe:
http://de.wikipedia.org/wiki/Dynamische_Programmieru…

was hast du denn genau vor?

So wie ich es gesagt habe, einen vollständig geklammerten ausdruck aus einer datei einlesen und dann ausrechnen.

z.b.:

((4+5)*8)
(((4+7)/10)*40)
als zeilen aus einer datei, die dann eingelesen werden und ohne trennungszeichen (leerzeichen) über das split in ein stringarray gepackt werden.
Sieht dann fuer den zweiten ausdruck so aus :

String [x]

[0] :frowning:
[1] :frowning:
[2] :frowning:
[3] :4
[4] :+
[5] :7

[n] :smile:

und dieses String array soll dann mit D&C so aufgeteilt und bearbeitet werden, das man den ausdruck stück fuer stück reduziert und ausrechnet.

LG

(((4+7)/10)*40)

Stell dir das ganze doch als Operator-Baum vor:

 \*
 / \
 : 40
 / \
 + 10
 / \
4 7

Bei jedem Operator im Baum kannst du einfach in linke und rechte Hälfte trennen und diese separat berechnen (divide). Dann hat dein Operator jeweils nur noch zwei Zahlen als Argument und das kannst du dann ja einfach ausrechnen. (conquer).

Wenn du z.B. folgendes Beispiel betrachtest, dann siehst du es besser:

(((4+7)-(3*2))+((9-4)*(6:3)))

 +
 / \
 - \*
 / \ / \
 + \* - :
 / \ / \ / \ / \ 
 4 7 3 2 9 4 6 3

Du könntest also erstmal alle Terme der Form (AxB) berechnen, wobei A,B Zahlen sind und x ein Operator (+,-,*,:,usw). Dies sind genau die Operationen im Baum, wo beide Kinder Blätter des Baumes sind.

Das kannst du z.B. ganz einfach mit regulären Ausdrücken machen, in dem du Terme der obigen Form suchst. Dann berechnest du den Ausdruck (der ja jetzt nur eine elementare Operation ist) und ersetzt den Ausdruck dann durch das Ergebnis.

Also bei

(((4+7)-(3*2))+((9-4)*(6:3)))

würdest du (4+7), (3*2), (9-4) und (6:3) z.B. mit RegEx herausfiltern, berechnen und durch das Ergebnis ersetzen. Danach sieht der Gesamterm dann so aus:

((11-6)+(5*2))

Dann machst du das gleiche wieder: (11-6) und (5*2) herausfiltern, berechnen und durch Ergebnis ersetzen. Macht also:

(5+10)

Das ganze wiederholst du so lange, bis kein geklammter Term mehr übrig ist und nur noch eine Zahl übrig ist. Wir brauchen also noch einen Schritt und berechnen jetzt (5+10). Bleibt 15 übrig und das ist dann das Gesamt-Ergebnis.

Insgesamt hast du dann also das komplexe Gesamt-Problem in lauter kleine Probleme zerlegt (divide) und diese zur Gesamtlösung wieder zusammengesetzt (conquer).

und dieses String array soll dann mit D&C so aufgeteilt und
bearbeitet werden, das man den ausdruck stück fuer stück
reduziert und ausrechnet.

Das wird kaum möglich sein, weil du aus deinem String-Array überhaupt nicht erkennen kannst, wie die Dinge verschachtelt sind.

1 Like

Hallo deconstruckt, hallo community,

danke fuer die unheimlich ausfuehrliche antwort. die vorstellung der baum strucktur hat mir im zusammenhang des algorithmus wirklich weitergeholfen. also ist der grundsätzliche ansatz schonmal klar geworden.

nun habe ich mich allerdings mit RegEx alias Reguläre Ausdrücke in java beschäftigt. Die ganze sache ist mir recht schwer gefallen und nach etlichen befragungen an google und zahlreichen deutschen wie englishen tutorials ist mir nicht ganz bewusst geworden wie ich das argument im petter zu beschreiben habe um einen ausdruck in der form (zahl"opperator"zahl) zu finden. auch das weiter arbeiten mit einem matsher in der form das ich den ausdruck berechnen und ersetzen kann ist mir nicht klar geworden…

es wäre unheimlich nett wenn die zeit gefunden werden könnte mir das mal zu verdeutlichen. syntaktisch gesehen ist mir die klasse regex schon bewusst, auch was sie tut ist einiger maßen klar geworden. allerdings ist die umsetzung auf mein problem fuer mich eine schwierigkeit : /

danke schon mal fuer eure besherige und hoffentlich folgende hilfe

LG

David

ganz bewusst geworden wie ich das argument im petter zu
beschreiben habe um einen ausdruck in der form
(zahl"opperator"zahl) zu finden. auch das weiter arbeiten mit

Am einfachsten ist es, wenn du dir deine RegEx Ausdrücke online zusammenbastelst. Dort kannst du sofort sehen, ob dein RegEx das macht, was du willst. Am besten fängst du immer ganz einfach an, also z.B. erstmal ne Klammer gefolgt von ner Zahl zu erkennen. Dann kannst du den Ausdruck Schritt-für-Schritt schwieriger machen.

Testen kannst du das z.B unter nachfolgendem Link. Die Seite benutzt auch Java dafür, deshalb kannst du davon ausgehen, dass der RegEx auf der Seite 1:1 auch in deinem Java-Programm funktionieren wird.
http://www.fileformat.info/tool/regex.htm
Einfach in das Feld Regular Expression deinen RegEx eingeben und dann kannst du unten mehrere Test-Strings eingeben, an denen du den RegEx testen kannst.

Wenn du das Schritt für Schritt bastelst, dann ist das nicht so schwer:

  1. Ein RegEx der eine Zahl erkennt. Das + gibt an, dass 0-9 mindestens einmal vorkommen muss. Der Ausdruck erkennt also z.B. 4,0,243,32

    [0-9]+

  2. Nun wollen wir einen RegEx der einen Operator erkennt. Normal kann man in eckigen Klammern einfach Zeichen aufzählen, also z.B. [±*/]. Da aber +,*,/ alles Sonderzeichen in RegEx sind muss man sie „escapen“, in dem man ihnen einen Backslash voranstellt. Der RegEx der also einen Operator (+,-,*,/)erkennt lautet daher dann:

    [+-*/]

  3. Jetzt können wir einfach Zahl/Operator/Zahl erkennen, in dem wir die obigen RegEx einfach kombinieren:

    [0-9]+[+-*/][0-9]+

  4. Nun fehlen nur noch die Klammern vorne und hinten, die man mit ( bzw ) angeben kann. Die muss man auch escapen, weil Klammern ebenfalls Sonderzeichen in RegExen sind. Insgesamt ergibt sich dann folgender Ausdruck:

    ([0-9]+[+-*/][0-9]+)

Unter folgendem Link kannst du den Ausdruck direkt testen an (((4+7)/10)*40) und an (((12+5)-(3*2))+((9-41)*(6/3)))

http://www.fileformat.info/tool/regex.htm?regex=%28…

In ersterem findet der RegEx korrekterweise nur (4+7). In zweiterem Beispiel findet er dagegen (12+5), (3*2), (9-41) und (6/3). Das gibt dir die Seite nach der Auswertung in der Spalte „group(0)“ an.

einem matsher in der form das ich den ausdruck berechnen und
ersetzen kann ist mir nicht klar geworden…

Naja, du kannst mit dem Matcher einfach mit der find()-Methode dir alle Fundstellen ausgeben lassen. Die kannst du dann ja berechnen und du könntest die dann in einer Kopie des Strings einfach mit replaceAll() ersetzen. Also z.B. so:

String original = "(((12+5)-(3\*2))+((9-41)\*(6/3)))";
String input = original;
Pattern p = Pattern.compile("\\([0-9]+[\\+\\-\\*\\/][0-9]+\\)");
Matcher m = p.matcher(input);

while (m.find()) {
 String treffer = input.substring(m.start(), m.end());
 int teilErgebnis = berechne(treffer);
 System.out.println(treffer + " = " + teilErgebnis);
 original.replaceAll(treffer, teilErgebnis+"");
}

Hallo,

Das mit den RegEx funktioniert wirklich wunderbar ! Ist ne tolle sache, nur ich scheine an einer stelle einen fehler zu machen.

Ich will nun den vom ersten Matscher Reduzierten Klammerausdruck nochmal mit RegEx zerlegen und in String Arrays stecken um sie dann zu berechnen.

Also sollte folgendes Passieren:

String = (x+y)

String a [1] = x
String a [2] = y

String b [1] = +

mein Problem an der stelle ist, das ich nicht den opperator in „b“ bekomme sondern mir eine zahl reingeschriben wird… ich hab keine ahnung wieso das passiert ^^

der zweck soll sein dass man später mit parseInt an die zahlen ran kommt und mit equals den opperator vergleichen kann.

meine Code überlegung dazu:




String a = b;
String c = b;
int zahl1 = 0;
int zahl2 = 0;
int ergebniss = 0;
int i = 1;
String z;
String [] zahlen = new String[5];
String [] opperanten = new String[5];

//Pattern args. | Constructor
Pattern p = Pattern.compile("[0-9]+");
//Matcher Constructor
Matcher m = p.matcher(a);



//extract numbers
while(m.find()){

zahlen[i]=a.substring(m.start(), m.end());

i++;

}



//Pattern args. | Constructor
Pattern pp = Pattern.compile("[\*\-\/\+]");
//Matcher Constructor
Matcher mp = p.matcher©;



//extract operators
while(mp.find()){
opperanten[1]=c.substring(mp.start(), mp.end());
}




//Pattern args. | Constructor
Pattern pp = Pattern.compile("[\*\-\/\+]");
//Matcher Constructor
Matcher mp = p.matcher©;

Du nimmst beim Matchen auf den Operator das alte Pattern p her. Du müsstest aber pp.matcher© verwenden.

Danke !! das war es es läuft alles!!

LG David