TStack, Infix zu Postfix, Strings ausrechnen

Übersicht BlitzMax, BlitzMax NG Codearchiv & Module

Neue Antwort erstellen

Xeres

Moderator

Betreff: TStack, Infix zu Postfix, Strings ausrechnen

BeitragFr, März 29, 2013 1:01
Antworten mit Zitat
Benutzer-Profile anzeigen
Worum geht es hier?
Ab und an kann es vorkommen, dass man eine Eingabe oder Formel wie aus einer Datei berechnen möchte. Wenn man keine Scriptsprache wie Lua bemühen kann oder will, kommt man vielleicht auf die Idee, einen Parser für Formeln zu schreiben. Tatsächlich kann man es sich aber viel einfach machen.
Dazu braucht man Drei Dinge: Einen Stack, eine Funktion die den String in eine Postfix Notation überführt und schließlich eine Funktion, die das ganze ausrechnet.

Code (mit Beispiel)
Der Code enthält einige Kommentare, um die Funktionsweise etwas näher zu erklären. Am Ende befindet sich der Beispiel Code zur Anwendung.
BlitzMax: [AUSKLAPPEN]
SuperStrict

Rem
Als erstes brauchen wir einen generellen LIFO Stack
LIFO: Last in, First Out
d.h. das erste element wird in den stack gepusht,
dann das zweite. Das zweite liegt nun oben, wird
als erstes wieder gepoppt, zuletzt wird das erste
Element wieder gepopt.
endrem

Type TStack

rem
Man könnte den Stack auch mit einem Array realisieren.
Dann müsste man aber aufs vergrößern/verkleinern achten.
endrem

Field list:TList

Rem
Erstellt einen neuen, leeren Stack
endrem

Function Create:TStack()
Local s:TStack = New TStack
s.list = New TList
Return s
End Function

Rem
Legt einen Wert auf den Stack.
Lasst euch nicht von "Last" verwirren - hauptsache
ist, dass man weiß, welche Seite "oben" sein soll
endrem

Method Push(_value:String)
Self.list.AddLast(_value)
End Method

Rem
Liefert den Wert oben auf dem Stack ohne ihn zu
entfernen.
endrem

Method Peek:String()
Return String(Self.list.Last())
End Method

Rem
Liefert den Wert oben auf dem Stack und löscht
ihn dabei vom Stack.
endrem

Method Pop:String()
Local val:String = String(Self.list.Last())
Self.list.RemoveLast()
Return val
End Method

Rem
Servicewrapper um die Anzahl der Elemente im
Stack zu erhalten.
endrem

Method Count:Int()
Return Self.list.Count()
End Method

Rem
Servicewrapper um einen Stack zu leeren.
endrem

Method Clear()
Self.list.Clear()
End Method

Rem
Servicewrapper um einen neuen Stack mit gleichem
Inhalt zu erhalten.
Endrem

Method Copy:TStack()
Local s:TStack = New TStack
s.list = Self.list.Copy()
Return s
End Method

Rem
Hauptsächlich zu debugging zwecken:
Gibt den Inhalt des Stacks aus, ohne ihn zu ändern.
Werte werden durch ein Pipe getrennt ausgegeben
endrem

Method ToString:String()
Local out:String[]
For Local s:String = EachIn Self.list
out:+[s]
Next
Return "|".join(out)
End Method

Rem
Hauptsächlich zu debugging zwecken:
Pusht mehrere Strings hintereinander auf
den Stack.
endrem

Method MultiPush(_values:String[])
For Local s:String = EachIn _values
Self.Push(s)
Next
End Method

Rem
Servicewrapper der den Stack umkehrt
endrem

Method Reverse()
Self.list.Reverse()
End Method

Rem
Generiert aus einem Mathematischen Ausdruck in Infix
Notation einen in Postfix notation.
Beispiel:
Infix = "2 + 6 * 2 - 1"
Postfix = "2 6 2 * + 1 -"
endrem

Function InfixToPostfix:TStack(_infix:String)

'* Prepare String:
'Print("Infix (source): ~q" + _infix + "~q")

rem
Hier wird der String so vorbereitet, dass er
an Leerzeichen gebrochen wird. Neue Operatoren
und Funktionen müssen hier eingetragen werden.
EndRem

_infix = _infix.ToLower()
_infix = _infix.Replace(" ", "")
_infix = _infix.Replace(",", ".") '* Erkenne kommas als kommastellen...
For Local s:String = EachIn["+", "-", "*", "/", "^", "(", ")", "sqrt", "exp", "sin", "cos"]
_infix = _infix.Replace(s, " " + s + " ")
Next
_infix = _infix.Replace(" ", " ")
_infix = _infix.Trim()

'Print("Infix (prepared): ~q" + _infix + "~q")

'* Platz für Ergebnis und Operatoren:
Local result:TStack = TStack.Create()
Local OpStack:TStack = TStack.Create()

'* Wir brauche die Prioriät der Operatoren später;
Local OpVal:Tmap = New Tmap
OpVal.Insert("+", "1")
OpVal.Insert("-", "1")
OpVal.Insert("*", "2")
OpVal.Insert("/", "2")
OpVal.Insert("^", "3")
OpVal.Insert("sqrt", "3")
OpVal.Insert("exp", "3")
OpVal.Insert("sin", "3")
OpVal.Insert("cos", "3")
'* Klammern haben immer die höchste Priorität!
OpVal.Insert("(", "9")
OpVal.Insert(")", "9")

'* String in seine einzelteile zerlegen:
Local source:String[] = _infix.Split(" ")

For Local symbol:String = EachIn source

'Print("Sy: " + symbol + "~t~tRe: " + result.ToString() + "~t~tOp:" + OpStack.ToString())

Select symbol

Rem
Öffnende Klammern und unäre Operatoren (Funktionen, die einen
einzelnen Wert bearbeiten) kommen immer auf
den Operator Stack.
endrem

Case "(", "sqrt", "exp", "sin", "cos"
OpStack.Push(symbol)

Rem
Schließende Klammern verschieben Operatoren
auf den Ergebnis Stack, bis sie auf eine
öffnende Klammer stoßen.
Endrem

Case ")"
While (OpStack.Peek() <> "(")
result.Push(OpStack.Pop())
Wend
OpStack.Pop() '* Pop '('

Rem
Linksassoziative Operatoren verschieben zuerst alle Operatoren
gleicher oder höherer Priorität auf den Ergebnis Stack - von
Klammern abgesehen. Dann werden Sie auf den Operator Stack
gelegt.
endrem

Case "+", "-", "*", "/"
Local SymbolPrio:Int = OpVal.ValueForKey(symbol).ToString().ToInt()
While (OpStack.Count() > 0 And OpStack.Peek() <> "(" And SymbolPrio <= OpVal.ValueForKey(OpStack.Peek()).ToString().ToInt())
result.Push(OpStack.Pop())
Wend
OpStack.Push(symbol)

Rem
Rechtsassoziative Operatoren verschieben unäre Operatoren
auf den Ergebnis Stack. Dann werden Sie auf den Operator
Stack gelegt.
Endrem

Case "^"
While (OpStack.Count() > 0)
Select OpStack.Peek()
Case "sqrt", "exp", "sin", "cos"
result.Push(OpStack.Pop())
Default
Exit
End Select
Wend
OpStack.Push(symbol)

Rem
Zahlen -und alle unbekannten symbole! - werden auf den
Ergebnis Stack gelegt.
Endrem

Default
result.Push(symbol)
End Select

Next

Rem
Alle übrig gebliebenen Operatoren werden
auf den Ergebnis Stack gelegt.
endrem

While (OpStack.Count() > 0)
result.Push(OpStack.Pop())
Wend

Return result
End Function

Rem
Der Stack muss als Postfix vorliegen!
Dann kann diese Methode den Ausdruck berechnen
Endrem

Method Calc:Double()
Local _stack:TStack = Self.Copy() '* Arbeitskopie anfertigen
_stack.Reverse() '* Für die Berechnung 'hinten' anfangen...
Local calcStack:TStack = TStack.Create() '* Ein Stack um die Zahlen zu verrechnen

'Print("Calc: " + _stack.ToString())

While (_stack.Count() > 0)

'Print("Stack: " + _stack.ToString())
'Print("CStack: " + CalcStack.ToString())
'Print("Symbol: " + _stack.Peek())

Rem
Falls es sich um das aktuelle symbol auf dem
Stack um einen Operator oder eine Function
handelt, nimm Zahlen aus dem Stack, rechne
das Ergebnis aus und lege es zurück auf den Stack.
endrem


Select _stack.Peek()

Case "exp"
_stack.Pop()
Local a:Double = CalcStack.Pop().ToDouble()
CalcStack.Push(Double(Exp(a)))

Case "sqrt"
_stack.Pop()
Local a:Double = CalcStack.Pop().ToDouble()
CalcStack.Push(Double(Sqr(a)))

Case "cos"
_stack.Pop()
Local a:Double = CalcStack.Pop().ToDouble()
CalcStack.Push(Double(Cos(a)))

Case "sin"
_stack.Pop()
Local a:Double = CalcStack.Pop().ToDouble()
CalcStack.Push(Double(Sin(a)))

Case "^"
_stack.Pop()
Local a:Double = CalcStack.Pop().ToDouble()
Local b:Double = CalcStack.Pop().ToDouble()
CalcStack.Push(b ^ a)

Case "*"
_stack.Pop()
Local a:Double = CalcStack.Pop().ToDouble()
Local b:Double = CalcStack.Pop().ToDouble()
CalcStack.Push(b * a)

Case "/"
_stack.Pop()
Local a:Double = CalcStack.Pop().ToDouble()
Local b:Double = CalcStack.Pop().ToDouble()
CalcStack.Push(b / a)

Case "+"
_stack.Pop()
Local a:Double = CalcStack.Pop().ToDouble()
Local b:Double = CalcStack.Pop().ToDouble()
CalcStack.Push(b + a)

Case "-"
_stack.Pop()
Local a:Double = CalcStack.Pop().ToDouble()
Local b:Double = CalcStack.Pop().ToDouble()
CalcStack.Push(b - a)

?Debug
Case ""
RuntimeError("CalcStack : Empty Stack Entry")
?

Rem
Falls es keine bekannte Funktion/Operator war,
nehmen wir an, es handelt sich um eine Zahl die
auf dem Stack gespeichert wird.
endrem

Default
CalcStack.Push(_stack.Pop())
End Select

Wend

?Debug
rem
Falls sich nach der rechnerei noch mehr als eine Zahl auf dem Stack befinden,
muss etwas schief gegangen sein...
endrem

If calcStack.Count() > 1 Then RuntimeError("CalcStack : Malformed Infix Stack")
?

'* Das Endergebnis vom Stack holen:
Return calcStack.Pop().ToDouble()

End Method

Rem
Servicefunktion: Berechnet einfach einen String
indem der Ausdruck zu einem Stack verarbeitet und
dieser ausgerechnet wird.
endrem

Function Calculate:Double(_infix:String)
Return TStack.InfixToPostfix(_infix).Calc()
End Function

End Type

Rem
Oder auch für den ganz kurzen Aufruf wrappen:
Endrem

Function CalcI:Int(_str:String)
Return Int(TStack.InfixToPostfix(_str).Calc())
End Function

Local Stack:TStack = TStack.Create()
Local Infix:String = "2 + 6 * 2 - 1"
Stack = TStack.InfixToPostfix(Infix)
Local Postfix:String = Stack.ToString()
Print("Infix: " + Infix)
Print("Postfix: " + Postfix)
Print(" = " + Stack.Calc())
Print("")

Local form:String = "sqrt(sin(45*2) + 3*5)"
Print("Oder Kurz: " + form + " = " + CalcI(form))


Release Ausgabe:
Code: [AUSKLAPPEN]
Infix:   2 + 6 * 2 - 1
Postfix: 2|6|2|*|+|1|-
 = 13.000000000000000

Oder Kurz: sqrt(sin(45*2) + 3*5) = 4


Dokumentation
Das wichtigste in Kürze - fragt ansonsten nach:

InfixToPostfix:TStack(_infix:String)
Ein String mit einer handelsüblichen Formel wie z.B. "(3+2)*5" (Infix) wird so umgeschrieben, dass die Operatoren auf die Zahlen Folgen: "3 2 + 5 *" (Postfix). Ausgegeben wird das Ergebnis gleich als Stack.

Method Calc:Double()
...rechnet den zuvor generierten Stack aus.

Function Calculate:Double(_infix:String)
Function CalcI:Int(_str:String)

Diese Funktionen tun nicht mehr, als beide Aktionen nacheinander aus zu führen. Wer mit Stacks wenig bis nichts zu tun haben will, kann sie für seine Zwecke modifizieren.

Sonstiges
Wie schnell ist das ganze?
Ich habe keine Ahnung. Vielleicht geht es noch schneller, wenn man den Stack als Array realisiert. Und dann müsste man es gegen eine andere Rechenmethode testen...

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG Codearchiv & Module

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group