http://de.wikipedia.org/wiki/Umgekehrte ... e_Notation
Irgendwo in einem anderen Thread wurde das mal angesprochen.
Da ich es schon in meinem Compiler eingebaut hatte, hab ich es jetzt für
euch wieder rausgelesen und aufbereitet (v.a. vereinfacht).
Ich garantiere nicht für Fehlerlosigkeit, aber die erweiterte Version tuts für
mich bis jetzt fehlerlos
Der Hauptteil des Codes (bis Zeile 150) ist eigentlich irrelevant, er dient
nur zum aufteilen des Strings in Tokens.
Dann kommen etwa 100 Zeilen, die den Hauptalgorithmus ausmachen!
Code: Alles auswählen
Structure TOKENS
s.s ; Inhalt
Typ.s ; "op", "int", "par"
EndStructure
NewList Tokens.TOKENS()
Procedure SCIsOperator(s.s)
Protected ReturnValue.l
;/ überprüft ob es ein bekannter Operator ist
ReturnValue = #False
If Len(s) = 1
Select PeekB(@s)
Case '+'
ReturnValue = #True
Case '-'
ReturnValue = #True
Case '*'
ReturnValue = #True
Case '/'
ReturnValue = #True
EndSelect
EndIf
ProcedureReturn ReturnValue
EndProcedure
Procedure SCIsKlammer(s.s)
Protected *p.BYTE, ReturnValue.l
;/ Ist es eine Klammer?
If Len(s) = 1
*p = @s
ReturnValue = #False
If *p\b = '(' Or *p\b = ')'
ReturnValue = #True
EndIf
EndIf
ProcedureReturn ReturnValue
EndProcedure
Procedure SCIsInteger(s.s)
Protected *p.BYTE, ReturnValue.l
*p = @s
;/ Ist es eine Zahl
ReturnValue = #False
If *p\b <> 0
While *p\b <> 0
If (*p\b < 48 Or *p\b > 57)
Break
EndIf
*p + 1
Wend
If *p\b = 0 And *p\b <> @s + 1
ReturnValue = #True
EndIf
EndIf
ProcedureReturn ReturnValue
EndProcedure
Procedure CleanSCOutput()
;/ Fügt mehrziffrige Zahlen zusammen
;/ Die Zahl 23 ist im Moment noch in 2 Tokens unterteilt
Protected WasInt.l, LastInt.s
ForEach Tokens()
If Tokens()\Typ = "int"
If WasInt = #True
LastInt = Tokens()\s
DeleteElement(Tokens())
Tokens()\s + LastInt
EndIf
WasInt = #True
Else
WasInt = #False
EndIf
Next
EndProcedure
Procedure Scanner(String.s)
Protected Len.l, Start.l, z.l, s.s
;/ Zerlegt den String in die einzelnen Bestandtteile und
;/ schreibt sie in eine Liste
Len = Len(String)
Start = 1
; Den ganzen Ausdruck einklammern (für umgek. Polnische Notation nötig)
AddElement(Tokens())
Tokens()\s = "("
Tokens()\Typ = "par"
For z = 1 To Len + 1
s = ReplaceString( Mid(String, Start, z - Start), Chr(9), " ")
If s = " "
s = ""
Start + 1
ElseIf s = ""
Continue
ElseIf SCIsOperator(s)
AddElement(Tokens())
Tokens()\Typ = "op"
Tokens()\s = s
Start + 1
s = ""
ElseIf SCIsInteger(s)
AddElement(Tokens())
Tokens()\Typ = "int"
Tokens()\s = s
Start + Len(s)
s = ""
ElseIf SCIsKlammer(s)
AddElement(Tokens())
Tokens()\Typ = "par"
Tokens()\s = s
Start + 1
s = ""
EndIf
Next
AddElement(Tokens())
Tokens()\s = ")"
Tokens()\Typ = "par"
CleanSCOutput()
EndProcedure
;- Hauptteil zur umgekehrten Polnischen Notation
NewList Symbols.TOKENS()
NewList PStack.TOKENS()
Procedure GetPrecedence(*Token.TOKENS)
Protected ReturnValue.l
;/ Gibt die Priorität der Operatoren und Klammern zurück
Select *Token\Typ
Case "op"
Select *Token\s
Case "+"
ReturnValue = 3
Case "-"
ReturnValue = 3
Case "*"
ReturnValue = 4
Case "/"
ReturnValue = 4
EndSelect
Case "par"
ReturnValue = 5
EndSelect
ProcedureReturn ReturnValue
EndProcedure
Procedure PParseExpression()
;/ Hauptteil: Kehrt die Tokens gemäss Punkt-vor-Strich-Regel um.
;/ anstatt 3 + 4 steht dann 3 4 +
;/ oder 3 * (4 + 5) -> 3 4 5 + *
ClearList(Symbols())
ClearList(PStack())
ForEach Tokens()
If Tokens()\s = "("
; Lege auf Stack
AddElement(PStack())
PStack()\s = Tokens()\s
PStack()\Typ = Tokens()\Typ
ElseIf Tokens()\s = ")"
; Nehme so lange vom Stack bis wir bem Anfang
; des Klammernblockes sind
While PStack()\s <> "("
AddElement(Symbols())
Symbols()\s = PStack()\s
Symbols()\Typ = PStack()\Typ
DeleteElement(PStack())
Wend
If PStack()\s = "("
DeleteElement(PStack())
EndIf
ElseIf Tokens()\Typ = "op"
; Wenn es ein Operator ist
Repeat
; Wenn entweder Stack leer, auf Stack ne Klammer-Auf '('
; oder wenn das Zeichen auf dem Stack eine niedrigere
; Priorität besitzt als das aktuelle
If CountList(PStack()) = 0 Or PStack()\s = "(" Or GetPrecedence(@PStack()) < GetPrecedence(@Tokens())
; Lege aktuelles Element auf Stack und breche Schleife ab
AddElement(PStack())
PStack()\s = Tokens()\s
PStack()\Typ = Tokens()\Typ
Break
Else
; Schreibe es in Symbols rein
AddElement(Symbols())
Symbols()\s = PStack()\s
Symbols()\Typ = PStack()\Typ
DeleteElement(PStack())
EndIf
ForEver
Else
; Wenns ein Integer ist gleich in Symbols reinschreiben
AddElement(Symbols())
Symbols()\s = Tokens()\s
Symbols()\Typ = Tokens()\Typ
EndIf
Next
EndProcedure
Procedure OutputTokens()
ForEach Tokens()
Debug Tokens()\s
Next
EndProcedure
Procedure OutputSymbols()
ForEach Symbols()
Debug Symbols()\s
Next
EndProcedure
String.s = "3 + 4 * (5 + 23)"
Scanner(String)
Debug "##### Scanned #####"
OutputTokens()
PParseExpression()
Debug "##### Reversed #####"
OutputSymbols()greetz
Remi
Übrigens zum etwa 5. Male will ich wieder ein Theorie&Konzeptions-Forum!
