Römische Zahlen in Arabische Ziffern umgewandeln

[nini89]

komm mit dieser aufgabe gar nicht zurecht, vllt kann mir da jemand helfen??? BITTEEEEE


Mit einem Endlichen Automaten sollen Römische Zahlen in Arabische Ziffern umgewandelt werden. Hierbei sind nur Zahlen aus dem Intervall [1;10] (I, II, III, IV, V, VI, VII, VIII, IX, X) zu berücksichtigen. (Wer möchte darf gerne das Intervall erweitern.)

1. Wie lauten die Zustandsmenge und das Eingabealphabet des endlichen Automaten (schriftlich)?
2. Entwickeln und zeichnen Sie den Zustandsgraphen (schriftlich)!
3. Entwickeln Sie ein Java-Programm Automat.java, welches mit einem endlichen Automaten die Umwandlung vornimmt. Die Eingabe soll case-insensitiv sein. Lesen Sie jeweils einen einzelnen Buchstaben (I, V oder X) von der Tastatur und überführen Sie Ihren Automaten in einen neuen Zustand. Bei Eingabe eines ungültigen Zeichens soll eine RuntimeException geworfen werden. Wenn kein Zeichen eingegeben wird (also nur Return gedrückt wird), wird der Automat beendet und das Ergebnis ausgegeben.



1 und 2 hab ich glaub ich, aber wie 3 aussehen soll...ka

 

[0x7F800000]

1 und 2 hab ich glaub ich, aber wie 3 aussehen soll...ka

lol... wenn du schon den schwierigeren teil hast, dann tippe das 1:1 in java ein und gut iss? ???:L
(ein DEA sollte in java grad noch so umsetztbar sein^^ :roll: )
wenn du bei der konkreten umsetzung stress hast, dann dann kannst du dich ja bei konkreten problemen mit konkreten compilierbaren codestücken erneut ans forum wenden, da wird sicherlich dem einen oder dem anderen was einfallen, wie das jeweilige problem zu beheben ist...

 

[nini89]

wie den schwierigen teil???
Zustandsmenge ist bei mir {1,2,3,4,5,6,7,8,9,0}
und Eingabealphabet {I,V,X}

solange das nicht falsch ist wars ja net schwierig.

den graphen hab ich auch gezeichnet, ähnlich dem eines parkscheinautomaten(wikipedia), das war auch nicht so schwer.

nur leider hilft mir das für den code doch überhauptnicht.

 

[nini89]

ich bin wirklich am verzweifeln, unabhängig davon, dass es doch gar keinen sinn macht die aufgabe mit einem automaten zu lösen(nun gut, ist halt wieder ein an den haaren herbeigezogenes beispiel) weiss ich auch gar nicht was die besonderheit eines automaten in java ist.

es wird ja nicht sinn der sache sein, dass ich da jetzt 20 if-sätze einbaue...

 

[0x7F800000]

Also, irgendwie kommt mir die gesamte aufgabenstellung recht suspekt vor...

Wer möchte darf gerne das Intervall erweitern

Was für ein "Intervall" denn bitte... I-X erscheint mir ein wenig zu wenig. Um alle zahlen umrechnen zu können, die ohne allzu abgefahrene zeichen auskommen, also ungefähr ~100000, da würde imho ein DEA sowieso nicht ausreichen, da müsste man sich schon einen kellerautomaten für kontextfreie sprachen basteln, aber ich weiß im moment gar nicht, wie ich das für römische zahlen übehaupt anstellen sollte, dieses zahlensystem ist ja schon ziemlich bescheuert :roll: , auch ich würde mir nicht zum spaß einen abend zeit nehmen, um dieses problem zu lösen (obwohl meine vorstellungen von "Spaß" schon seltsam genug sind, wenn's um mathe geht^^)

deine wahl der zustandsmenge

{1,2,3,4,5,6,7,8,9,0}

erscheint mir noch suspekter, ich könnte mir fast denken, dass du einfach die kleine mächtigkeit der ergebnismenge ausnutzen willst, um alle möglichen fälle manuell abzuarbeiten, ohne das eigentliche problem an sich zu lösen.

Könntest du evtl. skizzieren, wie du den automaten in etwa konzipiert hast? ???:L

 

[0x7F800000]

ich bin wirklich am verzweifeln, unabhängig davon, dass es doch gar keinen sinn macht die aufgabe mit einem automaten zu lösen

naja, parser sind nun mal automaten...

was die besonderheit eines automaten in java ist.

Was für besonderheit? Es gibt keine besonderheit. Du kannst dir den automaten basteln wie du willst.

Im einfachsten fall kann man einen mehrdimensionalen char-array hinschreiben, wo die zustände gegen das eingabealphabet aufgetragen sind, und wo dann jedem so einem paar der nächste zustand zugeordnet wird (also diese "delta"-übergangsfunktion einfach in einer tabelle explizit angeben). Und dann plazierst du im startzustand nen zustandszeiger, und springst damit hin und her, bis die zeichenkette zu ende ist, dann gugst du nach, wo du am ende gelandet bist.

Im komplizierteren fall kannst du dir irgendeine klasse für einen Zustand anlegen, der in einer map referenzen zu anderen knoten des automaten speichert, und der dann per backtracking alle möglichen wege im nicht deterministischen fall abklappert, das wäre nicht sonderlich schnell, aber dafür recht simpel, und du bräuchtest den automaten nicht in die deterministische form übersetzen (was per hand nervig, per programm nicht trivial ist) Tipp: wenn die sprache nicht vorgegeben ist: mit prolog geht's wesentlich lustiger^^

kontextfreie sprachen parsen ist dann nochmal um paar größenordnungen spaßiger, kannst dir dann gerne selbst was drüber durchlesen, wenn du willst, ich halte lieber die klappe, weil ich selbst nicht mehr weiß, als in den anfängerbüchern steht, die ich mal von nem jahr durchgeblättert hab, will mich da grad nicht eindenken. Aber wenn du die aufgabe wirklich korrekt in allgemeiner form lösen willst, um alle römische zahlen von 1 bis paar millionen zu übersetzen, da musst du dir schon was einfallen lassen...

 

[nini89]

es sollen wirklich nur die zahlen I bis X ausgegeben werden, also 1 bis 10, deswegen auch meine Zustandsmenge (0 für 10), deswegen, sinn macht das programm keinen, soll wohl nur automaten näherbringen, aber ich weiss ja nichtmal wie so ein teil in java aussieht. skizze hab ich hier hinterlegt:

 

[nini89]

bei dem leeren kästchen fehlt noch ne 9

 

[nini89]

als beispiel: ich tippe 'I' enter, wo muss er dann was ändern? dann tippe ich 'X' enter und muss noch wo anders was ändern in dem array und dann wenn ich nur enter drücke muss er demnach '9' auswerfen...das wars... klingt einfach, wärs auch, wenn ich nicht nen automaten basteln müsste...

 

[Marco13]

Spontande, unfundierte Gedanken: Das mit der Zustandsmenge 0...9 klingt schon ein bißchen komisch. Ich gehe mal davon aus, dass die Eingabe zeichenweise verarbeitet wird - also werden diese Zustände nicht reichen.

Angenommen, die Eingabe ist IV. Dann wäre die Zustandsfolge ja z.B. sowas wie
1. Startzustand -> Lese ein zeichen, hier das "I"
2. Zustand, der beschreibt, dass ein "I" gelesen wurde -> Lese ein Zeichen, hier das "V"
3. Zustand, der beschreibt, dass ein "IV" gelesen wurde -> Lese ein Zeichen (Ende)
4. Endzustand: Ausgabe "4"

Bei der Eingabe "IX" wäre man bei Schritt 2 ja in einen anderen 3. Zustand gelangt
1. Startzustand -> Lese ein zeichen, hier das "I"
2. Zustand, der beschreibt, dass ein "I" gelesen wurde -> Lese ein Zeichen, hier das "X"
3. Zustand, der beschreibt, dass ein "IX" gelesen wurde -> Lese ein Zeichen (Ende)
4. Endzustand: Ausgabe "9"

Hm. Nur so eine Idee...

 

[nini89]

hmm, okay, also nur 6 zustände? bei VIII bräuchte man demnach doch 6? das ist schonmal n guter tipp, danke dir ^^ aber was ich noch nicht versteh ist wie das 2dimensionale char-array aussehen muss und mit welchem algorithmus ich dort zustände ändern soll und wie ich dann was ausgeben soll.

quasi weiss ich gar nichts und brauchs bis morgen früh...klasse.

 

[0x7F800000]

verflucht, warum lass ich mich dauernd auf sowas ein^^ ???:L

public class SmallRoman {

	// uebergangsfunktion definieren
	private static int[][] d=new int[][]{
		new int[]{1,2,3,-1,-1,6,7,8,-1,-1,-1},
		new int[]{5,4,-1,-1,-1,-1,-1,-1,-1,-1,-1},
		new int[]{10,9,-1,-1,-1,-1,-1,-1,-1,-1,-1}
	};
	
	// -1 bedeutet fehlerzustand
	private static int d(int state, char c){
		int symbol="IVX".indexOf(c);
		if(symbol>=0){
			return d[symbol][state];
		}else{
			return -1;
		}
	};
	
	public static int parseRoman(String s){
		int state=0; //startzustand
		for(int i=0; i<s.length(); i++){
			state=d(state,s.charAt(i)); //uebergang zum naechsten zustand
			if(state<0){
				throw new NumberFormatException("Dieser Mist ist keine roemische zahl zwischen I und X!");
			}
		}
		return state;
	}
	
	public static void main(String[] args) {
		String[] test=new String[]{"blah","X","III","IV","VIII","789","0.3E7","IX"};
		for(String s:test){
			System.out.print(s+"\t=\t");
			try{
				int i=parseRoman(s);
				System.out.print(i);
			}catch(NumberFormatException e){
				System.out.print(e.getMessage());
			}
			System.out.println();
		}
	}
}

edit:
Also, das ist jetzt im prinzip dein zustandsgraph als tabelle hingeschrieben. Mir ist unterwegs eigefallen, dass es wohl bisschen schöner wäre, die tabelle vertikal hinzuchreiben, dann sieht man direkter wo was ist, aber das ist egal, eifach alles transponiert denken...

 

[Gast]

mein held ^^ nur 2 sachen hatten wir noch gar nicht.
was ist parseRoman? und was tut catch?

 

[Gast]

bzw parseroman is ja nur die variable, habs gesehen

 

[0x7F800000]

throws spuckt exceptions, wenn irgendwas schief geht
catch fängt die exceptions wieder ein, wenn man glaubt, dass man mit den doch noch fertig wird.

kannst das alles weglassen, und bei ungültiger eingabe einfach -100 ausgeben oder irgendsowas...

 

[Gast]

ok, ungültige eingabe ist mir im moment egal, das kann ich nachher noch einbauen. kannst du vllt nochmal nur das grundprogramm posten? hab versucht das oben auszuführen, aber da fehlt doch sowas wie readChar, oder? weil wenn mans starten kommen nur 8 zeilen text und das programm ist zuende

 

[0x7F800000]

ach nee, komm,

BufferedReader reader=new BufferedReader(InputStreamReader(System.in));

in die main reinpacken und ein paar mal

reader.readLine()

aufrufen, und and parseRoman übergeben schaffst du ja wohl noch alleine, sonst wird's ja total witzlos... Also, zumindest mal ansatzweise müsste doch was gehen, wenn's stress gibt: mit konkreten problemen wieder hier nachfragen.

 

[Gast]

hehe, lach mich nicht aus, aber keine ahnung was das bedeutet...
ich kenn nur system.readInt bze system.readChar usw was ist ein bufferreader?

 

[0x7F800000]

ne, bei java wird niemand ausgelacht, wenn er mal ne klasse nicht kennt, davon gibts irgendwie paar hunderttausend in der api und noch teufel weiß wieviele in den ganzen anderen projekten, die nicht direkt von sun geleitet werden...

aber googln kann man's trotzdem, ob man's kennt oder nicht: "Einfache eingabe java" erster treffer