ProgrammieraufgabenHier wird regelmäßig eine neue Programmieraufgabe gestellt, die dann gelöst werden soll und in Zusammenarbeit mit den Moderatoren auch besprochen werden kann.
"Aus klein mach groß": Teil4- Zahlen anordnen
Diskussion: "Aus klein mach groß": Teil4- Zahlen anordnen im Forum Programmieraufgaben, in der Kategorie Code Kitchen; Anzeige
Dies ist die abschließende Aufgabe aus der Reihe "Aus klein mach groß" und basiert auf
"Aus klein mach groß": ...
Teilaufgabe a)
Infixterm nach Postfix (UPN) umwandeln.
wir alle kennen Infixnotation für "normale" Rechenvorgänge:
1+2+4 oder (2+3)*(6+7) Infixnotation heißt eigentlich, dass Operatoren(+*-) zwischen den Operanden stehen: 1+2
Hier "Aus klein mach groß": Teil3 - Rechnen mit Zahlen haben wir schon eine andere Notation kennengelernt und auch gesehen, dass das Abarbeiten solcher "Rechenanweisungen" in der UPN Notation programmiertechisch vergleichsweise einfach umgesetzt werden kann. Die Programme aus "Aus klein mach groß": Teil3 - Rechnen mit Zahlen können Benutzereingaben in solcher Form entgegennehmen und ausrechnen. Allerdings ist es für den Benutzer sehr gewöhnungsbedürftig, seine Terme erstmal in diese Form zu bringen - das wollen wir jetzt "übernehmen" .
Jetzt muss man aber dararuf achten, dass alle Zahlen korrekt eingegeben werden - uneindeutige Eingabeformen wie 123.123.132 sollten mit einer Fehlermeldung (am besten mit dem genaueren Stellenhinweis) quittiert werden, da der Benutzer durchaus 123.123+.123 gemeint haben könnte und sich vertippt hat.
Weiterhin muss man die Prioritäten der einzelnen Rechenzeichen beachten: - * / vor + - und () sind "am mächtigsten"
akzeptiert werden sollten: Operatoren: + - * / und ( )
akzeptierte Zahlenformen: 123; 123.123; .123
zwischen einzelnen Operatoren/Operanden kann (muss aber nicht) ein Leerzeichen stehen: 123+321;123 + 321; ( 123+ 321)
Großteil der Anforderungen mussten ja schon in ttp://www.hackerboard.de/thread.php?threadid=31713 erfüllt werden.
Einschränkungen:
Ihr braucht negative Zahlen nicht zu erkennen, diese sollte der Benutzer in Form (0-123) oder 0-123 eingegeben (also als Null minus Zahl) .
Ihr könnte allerding trotzdem eine Erkennung basteln .
Am einfachsten (imho) wäre es dazu, dem Benutzer die gewünschte Form für negative Zahlen mitzuteilen (z.B immer (-Zahl) und diese Erkennung vor der Umwandlung von Infix nach UPN laufen zu lassen wobei dann alle Vorkommen von (-Zahl) durch (0-Zahl) ersetzt werden.
allgemeine Vorgehensweise:
Benötigt: OperatorenStack.
gehe einen Term von links nach rechts durch.
- Eine Zahl kann direkt in den Ausgabestring kopiert werden.
- eine '(' wird immer auf dem Stack abgelegt
- wenn eine ')' vorkommt, so werden alle Operatoren solange vom Stack entfernt und in den Ausgabestring kopiert, bis eine ')' vorkommt. Diese wird anschließend aus dem Stack entfernt (ohne in die Ausgabe kopiert zu werden).Ist der Stack leer und eine ')' kam nicht vor, so war die Eingabe fehlerhaft ;)
- 1. ist das aktuelle Zeichen ein Operator, so prüfe den Top-Operator im Stack:
-- Stack leer -> lege den Operator ab
-- Top-Operator im Stack hat höhere oder gleiche Priorität -> pope diesen aus dem Stack in die Ausgabe. Gehe wieder zum schritt 1 (Operatorenvergleich)
-- Top-Operator im Stack ist eine '(' -> lege den aktuellen Operator auf den Stack
-- Top-Operator im Stack hat kleinere Priorität ->lege den aktuellen Operator auf den Stack ab
Ende des Terms erreicht: pope alle Operatoren vom Stack zur Ausgabe, ist eine '(' dabei, so war die Eingabe fehlerhaft ;)
Teilaufgabe b)
Verbinde dieses Modul mit dem aus "Aus klein mach groß": Teil3 - Rechnen mit Zahlen
Da dieses per Aufgabenstellung einen String entgegen nimmt, sollten dabei keine Probleme auftreten
Funktioniere die Ausgabeoption des UPN moduls so um, dass dem Benutzer auf Wunsch die Zwischenrechnungen des UPN Moduls ausgegeben werden.
Fange die Division durch 0 ab (Programm soll nicht abstürzen/unerwartet terminieren).
Aus diesen "Einzelteilen" ist nun ein Taschenrechner entstanden, der ein bisschen mehr kann, als die Standarddinger aus den Bücheraufgaben .
Wenn bei der Umsetzung nichts schiefgelaufen ist, so sollten Terme wie (2.8+8 )*(3+7/2.9)-(456.1128*102)/*1337
anstandslos akzeptiert und ausgerechnet werden können.
Optional: man kann auch COS/TAN /MOD /POW hinzufügen. Beim umwandeln von Infix zu UPN kann man z.B COS durch 'C' und TAN durch 'T' ersetzen und UPN Modul erweitern. Man kommt allerdings nicht umhin, ein paar Sonderregel für COS/TAN und weitere unäre (einstellige) Operatoren hinzuzufügen: im UPN Modul darf bei diesen Operatoren nur ein Operand vom Stack geholt werden. Aber das ist wohl doch eine Aufgabe für Fortgeschrittene .
__________________ Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt.
So, meine Lösung ist jetzt endlich fertig. Ich hasse Klammern
Ich habe alles selbst implementiert (auch die String-to-Float-Funktion), und trotzdem scheint alles irgendwie zu funktionieren.
Spezialfunktionen wie POW und SQRT usw. habe ich erst mal ausgelassen, es funktionieren also nur die Grundrechenarten sowie Klammern.
Wer sich meinen Code anschaut wird allerdings verzweifeln. Ich hab mir echt Mühe gegeben, aber letztendlich ist nur ein irgendwie zusammengecodetes Stück wenig kommentiertes Durcheinander herausgekommen.
Übrigens, ich finde nicht, dass das noch Schwierigkeit 1 ist, im Vergleich zu den meisten anderen Schwierigkeit-1-Aufgaben. Naja, dann wünsche ich den anderen Anfängern noch viel Spaß beim Coden
Edit: Irgendwie hab ich Probleme mit den Dateianhängen...
Original von Eydeet
Übrigens, ich finde nicht, dass das noch Schwierigkeit 1 ist, im Vergleich zu den meisten anderen Schwierigkeit-1-Aufgaben. Naja, dann wünsche ich den anderen Anfängern noch viel Spaß beim Coden
Psst. Ich wollte eigentlich keinen verschrecken (außerdem war der Algo schon mehr oder weniger vorgegeben) - und man musste ja nicht so viel wie Du implementieren . Insoweit: klar, im Vergleich zu den anderen Aufgaben ist es schon anspruchsvoller - allerdings sollte es für Anfänger immer noch gut zu schaffen sein.
und da ich schon indirekt als Java-Fan abgestempelt werde: einen Non-Java Lösung
Stack
Code:
PARAMSIZE typedef BYTE
FLOATSIZE typedef REAL10
TRUE equ 1
FALSE equ 0
.data
stack_struct STRUCT
BP_ dd 0
SP_ dd 0
maxSize dd 0
stack_struct ENDS
.code
; #########################################################################
; Zweck: legt einen neuen Stack in einem Speicherbreich an (Speicherbereich muss vom Caller
; reserviert werden!)
; Parameter: stackAddr: Adresse des Speichers, der für den Stack genutzt werden soll
; diese Speicheradresse wird bei allen Stackoperationen erwartet
; stack_size=groesse des zur verfuegung gestellen Speichers
; Rueckgabe: keine
stackNew proc stackAddr:DWORD,stack_size:DWORD
assume ecx:PTR stack_struct
mov ecx,stackAddr
mov eax, ecx
add eax, sizeof stack_struct
mov [ecx].BP_,eax ;direkt nach Verwaltuntsstruktur beginnt der genutze Speicher
sub eax,sizeof PARAMSIZE
mov [ecx].SP_,eax
mov eax, ecx
add eax,stack_size
mov [ecx].maxSize,eax
ret
stackNew endp
; #########################################################################
; Parameter: stackAddr: Pointer auf den Stack, gleiche Adresse wie bei stackNew
; Parameter: es werden NUR BYTEs abgelegt
; Rueckgabe: keine
; Hint: vorher stackIsFull nutzen!
stackPush proc stackAddr:DWORD,param:PARAMSIZE
assume ecx:PTR stack_struct
mov ecx,stackAddr
mov edx,[ecx].SP_
add [ecx].SP_, sizeof PARAMSIZE
add edx, sizeof PARAMSIZE
mov al, param
mov PARAMSIZE ptr [edx],al
ret
stackPush endp
; Parameter: stackAddr: Pointer auf den Speicher, gleiche Adresse wie bei stackNew
; Rueckgabe: in EAX das oberste Stackelement
; Hint: vorher stackIsEmpty nutzen!
stackPop proc stackAddr:DWORD
assume ecx:PTR stack_struct
mov ecx,stackAddr
mov eax,[ecx].SP_
sub [ecx].SP_,sizeof PARAMSIZE
movzx eax,byte ptr[eax]
ret
stackPop endp
; Parameter: stackAddr: Pointer auf den Speicher, gleiche Adresse wie bei stackNew
; Rueckgabe: in EAX das oberste Stackelement
; Hint: vorher stackIsEmpty nutzen!
stackTop proc stackAddr:DWORD
assume ecx:PTR stack_struct
mov ecx,stackAddr
mov eax,[ecx].SP_
movzx eax,byte ptr [eax]
ret
stackTop endp
; Parameter: stackAddr: Pointer auf den Speicher, gleiche Adresse wie bei stackNew
; Rueckgabe: TRUE(=1), wenn leer, ansonsten FALSE(=0)
stackIsEmpty proc stackAddr:DWORD
assume ecx:PTR stack_struct
mov ecx,stackAddr
mov eax, FALSE
mov edx,[ecx].SP_
cmp edx,[ecx].BP_
jge @f
mov eax,TRUE
@@:
ret
stackIsEmpty endp
; Parameter: stackAddr: Pointer auf den Speicher, gleiche Adresse wie bei stackNew
; Rückgabe: TRUE(=1) wenn Stack voll, ansonsten FALSE (=0)
stackIsFull proc stackAddr:DWORD
assume edx:PTR stack_struct
mov edx,stackAddr
mov eax, FALSE
mov ecx,[edx].SP_
cmp ecx,[edx].maxSize
jb @f
mov eax,TRUE
@@:
ret
stackIsFull endp
; Parameter: stackAddr: Pointer auf den Speicher, gleiche Adresse wie bei stackNew
; Float in ST(0) erwartet
; Rückgabe: keine
; Hint: stackIsFull nutzen!
floatStackPush proc stackAddr:DWORD
assume edx:PTR stack_struct
mov edx,stackAddr
mov ecx,[edx].SP_
add ecx, sizeof FLOATSIZE
add [edx].SP_, sizeof FLOATSIZE
FSTP FLOATSIZE ptr[ecx]
ret
floatStackPush endp
; Parameter: stackAddr: Pointer auf den Speicher, gleiche Adresse wie bei stackNew
; Rueckgabe: Float in ST(0)
; Hint: vorher stackIsEmpty nutzen!
floatStackPop proc stackAddr:DWORD
assume edx:PTR stack_struct
mov edx,stackAddr
mov eax,[edx].SP_
sub [edx].SP_,sizeof FLOATSIZE
fld FLOATSIZE ptr [eax]
ret
floatStackPop endp
UPN Rechner
Code:
include \masm32\include\masm32.inc
includelib \masm32\lib\masm32.lib
NOT_ALLOWED_DOT equ 2
NOT_ALLOWED_TERMINAL equ 3
STACK_OVERFLOW equ 4
NOT_ENOUGH_OPERANDS equ 5
NOT_ENOUGH_OPERATORS equ 6
ZERO_DIV equ 7
PARAMSIZE typedef BYTE
FLOATSIZE typedef REAL10
MAX_NUM equ 256
TRUE equ 1
FALSE equ 0
PLUS equ '+'
MINUS equ '-'
MULF equ '*'
DIVF equ '/'
LEER equ ' '
.data?
floatStack FLOATSIZE(MAX_NUM) dup (?)
.code
;Param: input: String in UPNForm
;rückgabe: TRUE, wenn keine ungültigen Zeichen, ansonsten NOT_ALLOWED_TERMINAL
;und in ESI Stringstelle
;Erlaubte Zeichen: 0-9 */+-. Leerzeichen
checkInput proc input:DWORD
;check input auf unerlaubte Zeichen
mov esi,input
dec esi
xor eax,eax
CHECK_LOOP:
add esi,1
mov al,byte ptr [esi]
test al,al
jz CHECK_OUT
cmp al,' '
je CHECK_LOOP
cmp al,'*'
jb error
cmp al,'/'
jg isdigit
cmp al,','
je error
jmp CHECK_LOOP
isdigit:
cmp al,'9'
jg error
cmp al,'0'
jb error
jmp CHECK_LOOP
error:
mov eax,NOT_ALLOWED_TERMINAL
ret
CHECK_OUT:
mov eax,TRUE
ret
checkInput endp
; Berechnet UPN Ausdruck
; Parameter: input: String in UPN Form, output: Pointer zu 8Byte Speicher,
; die Antwort wird in diesen Speicher geschrieben
; callback: optional, gibt in ST(0),ST(1) die Operanden und in EAX den Operator zurück
; so dass die Operation auch angezeigt werden kann
; Return: TRUE oder Fehlercode, in ESI Fehlerstelle (optionale Auswertung)
computeUPN proc input:DWORD, output:DWORD, callback:DWORD
LOCAL numend:DWORD
LOCAL num:REAL8
LOCAL dots:DWORD
invoke checkInput,input
cmp eax,TRUE
je @f
ret
@@:
finit
invoke stackNew,addr floatStack,MAX_NUM
mov esi,input
mov edi,esi ;edi soll numzeiger sein, esi wird dann das Ende des num-Teilstrings anzeigen
dec esi
xor eax,eax
mov dots,0
PARSE_LOOP:
xor ebx,ebx
add esi,1
mov bl, byte ptr [esi]
test bl,bl ;string zu ende?
je PARSE_OUT
cmp bl,'.'
jne @f
add dots,1
cmp dots,1
je PARSE_LOOP ;ansonsten mehr als 1 Punkt - unerlaubtes format
mov eax,NOT_ALLOWED_DOT
ret
@@:
cmp bl,'9'
jg ASCII2FLOAT
cmp bl,'0'
jb ASCII2FLOAT
jmp PARSE_LOOP
ASCII2FLOAT:
mov dots,0
;in EDI ist Startadresse des Floatstrings, in ESI Endadresse
;push [esi] ;sichern
cmp edi,esi ;0 Zeichen lange Zahl?
je NO_FLOAT
;mov byte ptr [esi],0 ;mit 0 terminieren
invoke StrToFloat, edi,addr num
cmp eax,esi
jne NO_FLOAT
invoke stackIsFull,addr floatStack
cmp eax,TRUE
jne @f
mov eax,STACK_OVERFLOW
ret
@@:
fld num
invoke floatStackPush,addr floatStack
NO_FLOAT:
mov edi,esi ;
add edi,1 ;nächstes Zeichen vielleicht?
cmp byte ptr [esi],LEER
je PARSE_LOOP
invoke floatStackPop,addr floatStack
;wenn Stack leer, so nicht genug operanden
invoke stackIsEmpty,addr floatStack
cmp eax,TRUE
jne @f
mov eax,NOT_ENOUGH_OPERANDS
ret
@@:
invoke floatStackPop,addr floatStack
mov bl, byte ptr [esi] ;CASE:
cmp callback,0
je @f
mov eax,ebx ;Operation weitergeben
call callback
@@:
cmp bl,PLUS
jne @f
fadd
jmp OP_OK
@@:
cmp bl,MINUS
jne @f
fsub ST(0),ST(1)
jmp OP_OK
@@:
cmp bl,MULF
jne @f
fmul
jmp OP_OK
@@:
cmp bl,DIVF
jne @f
fdiv ST(0),ST(1)
fstsw ax
test ax,4
jz OP_OK
mov eax,ZERO_DIV
ret
@@:
OP_OK:
cmp callback,0
je @f
mov eax,'=' ;Ergebnis weitergeben
call callback
@@:
invoke floatStackPush, addr floatStack
jmp PARSE_LOOP
PARSE_OUT:
invoke floatStackPop,addr floatStack
invoke stackIsEmpty,addr floatStack
cmp eax,TRUE
je @f
mov eax,NOT_ENOUGH_OPERATORS
ret
@@:
mov ecx,output
fstp qword ptr[ecx]
mov byte ptr [edi],0
mov eax,TRUE
ret
computeUPN endp
infix zu UPN
Code:
NOT_ALLOWED_TERMINAL equ 3
STACK_OVERFLOW equ 4
RIGHT_PARENTHESIS_ERROR equ 8
LEFT_PARENTHESIS_ERROR equ 9
MAX_NUM equ 256
TRUE equ 1
FALSE equ 0
PLUS equ '+'
MINUS equ '-'
MULF equ '*'
DIVF equ '/'
LEER equ ' '
.data?
opStack db (MAX_NUM) dup (?)
.code
; Inputcheck
; Param: input: String in Infix Form
; Return: TRUE oder Fehlercode, in ESI Fehlerstelle (optionale Auswertung)
; Erlaubte Zeichen: +-+/.() Leerzeichen
checkInfixInput proc input:DWORD
mov esi,input
dec esi
xor eax,eax
CHECK_LOOP:
add esi,1
mov al,byte ptr [esi]
test al,al
jz CHECK_OUT
cmp al,' '
je CHECK_LOOP
cmp al,'('
jb error
cmp al,'/'
jg isdigit
cmp al,','
je error
jmp CHECK_LOOP
isdigit:
cmp al,'9'
jg error
cmp al,'0'
jb error
jmp CHECK_LOOP
error:
mov eax,NOT_ALLOWED_TERMINAL
ret
CHECK_OUT:
mov eax,TRUE
ret
checkInfixInput endp
; Überführt Infix zu UPN
; Parameter: input: String in Infix Form, output: String in UPN Form,
; Return: TRUE oder Fehlercode, in ESI Fehlerstelle (optionale Auswertung)
; Achtung: der Aufrufer hat dafür zu sorgen, dass output groß genug ist!
infixToUPN proc input:DWORD, output:DWORD
invoke checkInfixInput,input
cmp eax,TRUE
je @f
ret
@@:
invoke stackNew,addr opStack,MAX_NUM
mov esi,input
mov edi,output
dec esi
TRANS_LOOP:
add esi,1
mov bl,byte ptr [esi]
test bl,bl
je TRANS_OUT
cmp bl,'0'
jb isDot
cmp bl,'9'
jg @f
;ansonsten eine Ziffer
jmp COPY_TO_OUTPUT
isDot:
cmp bl,'.'
jne @f
COPY_TO_OUTPUT:
mov byte ptr [edi],bl ;Ziffer/Punkt->kopiere zur Ausgabe
add edi,1
jmp TRANS_LOOP
@@:
;ansonsten keine Ziffer->zahl zu ende, Leerzeichen einfügen
mov byte ptr [edi],LEER
add edi,1
cmp bl,'('
jne @f
invoke stackIsFull,addr opStack
cmp eax,TRUE
jne no_err
mov eax, STACK_OVERFLOW
ret
no_err:
invoke stackPush,addr opStack,bl
jmp TRANS_LOOP
@@:
cmp bl,')'
jne @f
POP_LOOP:
invoke stackIsEmpty,addr opStack
cmp eax,TRUE ;Stack leer -> ) Klammer zu viel
jne no_err2
mov eax, RIGHT_PARENTHESIS_ERROR
ret
no_err2:
invoke stackPop,addr opStack
cmp al,'('
je TRANS_LOOP
mov byte ptr[edi],al
add edi,1
jmp POP_LOOP
@@:
;hack um (-X) Zahlen zu akzeptieren
cmp bl,MINUS
jne no_neg
cmp byte ptr[esi-1],'('
jne no_neg
mov word ptr [edi]," 0"
add edi,2
no_neg:
TOP_LOOP:
invoke stackIsEmpty,addr opStack
cmp eax,TRUE
jne @f
PUSH_OP:
invoke stackPush,addr opStack,bl
jmp TRANS_LOOP
@@:
invoke stackTop,addr opStack
cmp al,'('
jne @f
invoke stackPush,addr opStack,bl
jmp TRANS_LOOP
@@:
cmp bl,MINUS
je @f
cmp bl,PLUS
je @f
HIGHER_PRIORITY_CHECK: ;weder plus noch minus, Priorität feststellen
cmp al, PLUS
je PUSH_OP
cmp al,MINUS
je PUSH_OP
@@:
invoke stackPop,addr opStack
mov byte ptr[edi],al
add edi,1
jmp TOP_LOOP
@@:
TRANS_OUT: ;input leer, also alles runterpopen
invoke stackIsEmpty,addr opStack
cmp eax,TRUE
je ENDE
invoke stackPop,addr opStack
cmp al,'('
jne @f
mov eax,LEFT_PARENTHESIS_ERROR
ret
@@:
mov byte ptr [edi],al
add edi,1
jmp TRANS_OUT
ENDE:
mov byte ptr [edi],0
mov eax,TRUE
ret
infixToUPN endp
infixToUPN endp
im ZIP ist das Ganze dann noch mit einer GUI zusammengebunden + rudimäntere Fehlerausgabe.
Sowohl eine Make.bat wie auch RADASM Projekt Dateien liegen bei dem Source bei, die Binary (OS:Win32) habe ich auch beigelegt, da wahrscheinlich nicht jeder MASM installiert hat.
Ausgabe der GUI: Postfixform, Rechenschritte, Endergebnis
EDIT: einen kleinen Hack hinzugefügt, um (-X) Zahlenangaben zu akzeptieren
EDIT2: die GUI etwas erweitert, so dass man auch UPN-Format eingeben - und damit auch üben kann
__________________ Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt.
21.05.07, 16:59
"Aus klein mach groß": Teil4- Zahlen anordnen 
.
. 
Linear-Darstellung
Ähnliche Themen 
