Rekursions Divide-and-Conquer < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:44 Mo 27.10.2008 | | Autor: | Raiden82 |
| Aufgabe | Ziel: In dieser Aufgabe sollen JAVA-Klassen erstellt werden, die den Wert eines vollstandig geklammerten
Arithmetischen Ausdruck berechnen.
Voraussetzung:
- Sie erhalten eine Datei mit 10 Beispielen fur vollstandig geklammerte Ausdrucke reprasentiert als
Strings. Beispiel: ( ( 12 + 3 ) * 7 )
- Ein vollstandig geklammerter arithmetischer Ausdruck besteht aus aus den Symbolen (; );+;-; *; :
und Integerzahlen, die als Strings angegeben werden. Bei der Division handelt es sich um die ganzzahlige
Division.
- Hinter jedem Symbol (; );+;-; *; : oder Integerzahlen folgt ein Leerzeichen. Der Ausdruck wird
durch den Zeilenumbruch in der Datei abgeschlossen.
Erwartete Ergebnisse:
1. Lesen Sie einen Arithmetischen Ausdruck aus der gegebenen Datei aus.
2. Bereiten Sie ihn geeignet fur die Berechnung auf.
3. Implementieren Sie Klassen, die nach dem Entwurfsprinzip Divide-and-Conquer den Wert des Ausdrucks
berechnen.
4. Geben Sie das Ergebnis in der folgenden Form aus: Wert von Ausdruck i: Ergebnis
5. Implementieren Sie einen Rahmen, der dafur sorgt, dass nacheinander alle Ausdrucke aus der Datei
ausgelesen und berechnet werden. |
Kann mir jemand da weiterhelfen, weiß grade nicht wie ich das Anfangen soll...
Was ich schon weiß.. ich muß die Textdatei als String auslesen das geht durch die Leerzeichen zwischen den Zeichen doch worein soll ich die Speichern...
Ich weiß auch noch nicht wie ich die klammern ausrechnen soll ?
Danke für die Hilfe
Dateianhänge:
Anhang Nr. 1 (Typ: txt) [nicht öffentlich]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:32 Di 28.10.2008 | | Autor: | Raiden82 |
import java.io.*;
public class Main {
/**
* @param args
*/
public static void main(String[] args)throws IOException
{
FileReader fr = new FileReader("Expression.txt");
BufferedReader br = new BufferedReader(fr);
String zeile = "";
String[]exp;
while( (zeile = br.readLine()) != null )
{
System.out.println(zeile);
exp = zeile.split(" ");
}
br.close();
}
}
So sieht die klasse jetzt aus Weiß einer wie ich nun im D&C die klammern berechne ?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:43 So 02.11.2008 | | Autor: | pape |
Hallo.
Ehe Du anfängst zu programmieren, solltest Du Dir vielleicht Gedanken darum machen, wie ein solcher Ausdruck allgemein aufgebaut sein kann und wie Du ihn im Computer speichern und damit auch auswerten kannst.
Für Ersteres würde ich Dir empfehlen ein Syntaxdiagramm anzufertigen. Tipp: Rekursion. Welche Operatoren binden stärker? Für jede Ebene kannst Du ein Syntaxdiagramm anlegen. Ein Anfang wäre:
AUSDRUCK
-- (+/-) --
| |
v |
------------------>(optional) Vorzeichen -------> TERM ---->
(Hier soll nach TERM optional wieder ein TERM kommen der mit +oder - verbunden sein muss... ist hier etwas schwer zu "malen" :D )
ein TERM wiederum besteht aus Faktoren, Faktoren aus Potenzen und Potenzen aus z.B. Klammern (die wieder einen Ausdruck enthalten können usw), Funktionen wie sin(Ausdruck), eine Zahl, eine Variable x usw.. jenachdem was Du alles brauchst.
Für jede dieser Stufen in einem arithmetischen Audruck kannst Du Dir ein solches Syntaxdiagramm malen und es zu einem großen zusammensetzen, dass sich dann AUSDRUCK schimpft ;)
Zu jeder dieser Ebenen kannst Du dann auch Algorithmen entwickeln, die den String danach auseinander nehmen (z.B.: nach einem * muss ein Faktor kommen, nach einem "(" muss ein Ausdruck kommen und anschließend ein ")").
---
Für die Speicherung der Daten ist z.B. ein binärer Baum einfach und übersichtlich zu implementieren.
Dabei kannst Du im Knoten den Verknüpfungsoperator speichern und im linken bzw rechten Teilbaum die Ergebnisse.
So sähe z.B. der Ausdruck 1+7*x in einem Binärbaum so aus:
+
1 *
7 x
Divide & Conquer macht nun folgendes: Zum Ausrechnen des Ausdrucks an der Stelle x=4 fängt er an der Wurzel an und findet ein "+". Dafür teilt er das Problem auf, in linke Seite des "+" und Rechte, welche er zuerst ausrechnen muss (Rekursion). Sind diese Probleme gelöst, so setzt er die beiden Teilergebnisse zusammen mit dem Operator + und gibt den Wert zurück.
Ebenso verhalten sich alle anderen Teilprobleme. Sie liefern eine Lösung für den Teilbaum und die Lösung am Wurzelknoten ist die finale Lösung.
Das Rekursionende ist bei Zahlen oder x erreicht. Da gibst Du einfach die Zahl oder halt den für x einzusetzenden Wert zurück.
Das praktische bzgl der Klammern ist dabei, dass die Klammern im Binärbaum gar nicht mehr benötigt werden, da sie implizit im Baum abgespeichert werden. So sähe der Binärbaum von obigem Ausdruck anders geklammert so aus: (1+7)*x
*
+ x
1 7
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:22 So 02.11.2008 | | Autor: | pape |
Hi.
Da Du von vollständig geklammerten Ausdrücken ausgehst und keine Variablen usw hast, ist Deine Aufgabe sogar um einiges einfacher. Die Syntax ist gegeben durch
S -> (S+S) | (S*S) | Zahl
Also jedes S besteht entweder aus (S+S), (S*S) oder einer Zahl. Diese Rekursion musst Du implementieren, um den Ausdruck auszuwerten.
Divide & Conquer hast Du in dem Moment, wo Du einen Klammer-Ausdruck auswerten möchtest. Du benötigst erst die Teilergebnisse.
|
|
|
|
