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] [EINKLAPPEN] SuperStrict
Type TStack
Field list:TList
Function Create:TStack() Local s:TStack = New TStack s.list = New TList Return s End Function
Method Push(_value:String) Self.list.AddLast(_value) End Method Method Peek:String() Return String(Self.list.Last()) End Method
Method Pop:String() Local val:String = String(Self.list.Last()) Self.list.RemoveLast() Return val End Method
Method Count:Int() Return Self.list.Count() End Method
Method Clear() Self.list.Clear() End Method
Method Copy:TStack() Local s:TStack = New TStack s.list = Self.list.Copy() Return s End Method
Method ToString:String() Local out:String[] For Local s:String = EachIn Self.list out:+[s] Next Return "|".join(out) End Method
Method MultiPush(_values:String[]) For Local s:String = EachIn _values Self.Push(s) Next End Method
Method Reverse() Self.list.Reverse() End Method
Function InfixToPostfix:TStack(_infix:String) _infix = _infix.ToLower() _infix = _infix.Replace(" ", "") _infix = _infix.Replace(",", ".") For Local s:String = EachIn["+", "-", "*", "/", "^", "(", ")", "sqrt", "exp", "sin", "cos"] _infix = _infix.Replace(s, " " + s + " ") Next _infix = _infix.Replace(" ", " ") _infix = _infix.Trim() Local result:TStack = TStack.Create() Local OpStack:TStack = TStack.Create() 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") OpVal.Insert("(", "9") OpVal.Insert(")", "9") Local source:String[] = _infix.Split(" ") For Local symbol:String = EachIn source Select symbol Case "(", "sqrt", "exp", "sin", "cos" OpStack.Push(symbol) Case ")" While (OpStack.Peek() <> "(") result.Push(OpStack.Pop()) Wend OpStack.Pop() 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) 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) Default result.Push(symbol) End Select Next While (OpStack.Count() > 0) result.Push(OpStack.Pop()) Wend Return result End Function
Method Calc:Double() Local _stack:TStack = Self.Copy() _stack.Reverse() Local calcStack:TStack = TStack.Create() While (_stack.Count() > 0) 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") ? Default CalcStack.Push(_stack.Pop()) End Select Wend ?Debug If calcStack.Count() > 1 Then RuntimeError("CalcStack : Malformed Infix Stack") ? Return calcStack.Pop().ToDouble() End Method
Function Calculate:Double(_infix:String) Return TStack.InfixToPostfix(_infix).Calc() End Function End Type
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] [EINKLAPPEN] 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...
|