"Aus klein mach groß": Teil4- Zahlen anordnen

CDW

CDW

0
Mitarbeiter
Dies ist die abschließende Aufgabe aus der Reihe "Aus klein mach groß" und basiert auf
"Aus klein mach groß": Teil3 - Rechnen mit Zahlen
"Aus klein mach groß": Teil2 - Zahlen und Satzzeichen
sowie
"Aus klein mach groß": Teil1 - Stack
Wie auch vorher richtet es sich primär an Anfänger - deshalb sind die Anforderungen und Grenzen etwas "enger" gesteckt.

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" ;).

Programmiere also ein Modul, welches "normale" Infixeingaben in UPN Form bringt und als String zurückgibt. Dazu kann man "Aus klein mach groß": Teil2 - Zahlen und Satzzeichen entsprechend erweitern/anpassen.

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.



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 ;).
 
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 :D

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 :D
Zum Vergrößern anklicken....
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 ;)

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
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
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

Akzeptierte Rechenzeichen:
Plus: +
Minus:-
Mult: *
Div: /
negative Zahlen: (-X)

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
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben