002
08.03.2003, 18:59 Uhr
~0xdeadbeef
Gast
|
Soweit ich weiss, ist das normale Verfahren, den String auf zwei Stacks zu legen (einen für Zahlen, einen für die Symbole) und die Gleichung so in eine Art auseinandergenommene Postfix-Notation zu zerlegen, die dann sehr simpel auszurechnen ist. Genauere Beschreibungen des Algorithmus stehen in ziemlich vielen Büchern über Programmierung, weil das ein sehr klassisches Beispiel ist. Wenn ich mich recht entsinne, gab es so eine Übung samt Lösung in "C++-Programmierung" von Andre Willms aus dem Addison-Wesley-Verlag, aber 100%ig weiß ich das grad nicht.
Die O-Zeit des Algorithmus dürfte linear mit der Länge des Strings steigen. Auf jeden Fall dauert es _deutlich_ länger (mit deutlich länger meine ich in diesem Fall einen Multiplikator irgendwo kurz vor unendlich), als wenn du die Gleichung fest einkompilierst. In dem Fall arbeitet das Ding auch mit konstanter O-Zeit und ist innerhalb weniger Rechenschritte fertig, wenn du das ganze durch nen Matheparser laufen läßt, musst du sowohl die Rechnung, die du andernfalls fest einkompiliert hättest, durchführen, als auch den String zu parsen und zwei Stacks zu verwalten. Mehr Arbeit dauert halt auch länger.
Ein Mathe-Parser macht nur dann Sinn, wenn der User dir vorgibt, welche Gleichung du ausrechnen sollst, ansonsten bist du besser damit bedient, die Gleichung fest einzukompilieren.
Leitregel an der Stelle: Wenn du Performance willst, mach soviel wie möglich zur Compilezeit. Ein wunderbares Beispiel für performanten Code gibt es hier: http://community.borland.com/article/print/0,1772,10526,00.html - auch wenn darunter in diesem Fall die Übersichtlichkeit extrem leidet. |
