Obliczanie wyrażeń matematycznych ONP w Delphi
W pierwszej części artykułu pokazałem jak zaimplementować parser dokonujący konwersji z tradycyjnego wyrażenia algebraicznego, na postać ONP. W tej części uzupełnimy definicję metody obliczającą to wyrażenie oraz zaimplementujemy podstawowe funkcje matematyczne.
Funkcje matematyczne
Celem naszego parsera jest to, żeby obsługiwał dowolne funkcje matematyczne bez potrzeby modyfikacji jego kodu. Na początku zdefiniujemy sygnaturę funkcji matematycznych, które będą odpowiedzialne za wykonanie konkretnych operacji (takie jak dodawanie, mnożenie itd.). Następnie te funkcje opakuje się w interfejs, który będzie dostarczał te funkcje parserowi. Pozwoli to na dynamiczne rejestrowanie funkcji, a więc na łatwą rozbudowę parsera o możliwości obsługi nowych wzorów.
Prototyp funkcji
Na początku zdefiniujemy prototyp funkcji jako typ. Wszystkie implementowane funkcje matematyczne będą tego typu. Pierwszy argument będzie zawierał definicję funkcji, drugi natomiast listę argumentów niezbędnych do obliczenia wyniku.
Uzupełnij dodatkowe typy w module MathObjects.pas.
TMathArgs = Generics.Collections.TList<TMathObject>;
TMathFunc = function(Functor: TMathObject; Args: TMathArgs): Double of object;
Dla każdej funkcji należy zdefiniować nazwÄ™, po której parser ma jÄ… wywoÅ‚ywać oraz ilość argumentów, które majÄ… zostać zdjÄ™te ze stosu i przekazane jako argumenty funkcji. PrzykÅ‚adowo funkcja “NEG” negujÄ…cÄ… wynik wyrażenia, przyjmie tylko jeden argument.
Definicja pakietu funkcji
TMathBind = record
Name: string;
Func: TMathFunc;
ArgsCount: Integer;
constructor Create(const AName: string; const AFunc: TMathFunc;
const AValue: Integer);
end;
constructor TMathBind.Create(const AName: string; const AFunc: TMathFunc;
const AValue: Integer);
begin
Name := AName;
Func := AFunc;
ArgsCount := AValue;
end;
Oraz definicja interfejsu, który będzie implementować każda klasa, dostarczająca kolekcję funkcji matematycznych.
TMathFunctions = Generics.Collections.TList<TMathBind>;
IMathProvider = interface
function MathFunctions(): TMathFunctions;
end;
Implementacja podstawowych funkcji matematycznych
W tej sekcji zdefiniujemy dostawcę podstawowych funkcji matematycznych. W tym celu wykorzystamy interfejs IMathProvider, który będzie implementowany przez klasę TArithmeticProvider zwracając kolekcję pakietów typu TMathBind.
Deklaracja klasy dostawcy
type
TArithmeticProvider = class(IMathProvider)
protected
Funcs: TMathFunctions;
public
constructor Create;
destructor Destroy; override;
function MathFunctions(): TMathFunctions;
class function Add(Functor: TMathObject; Args: TMathArgs): Double;
class function Sub(Functor: TMathObject; Args: TMathArgs): Double;
class function Divide(Functor: TMathObject; Args: TMathArgs): Double;
class function Multi(Functor: TMathObject; Args: TMathArgs): Double;
class function Power(Functor: TMathObject; Args: TMathArgs): Double;
class function Negate(Functor: TMathObject; Args: TMathArgs): Double;
end;
Definicje metod interfejsu
constructor TArithmeticProvider.Create;
begin
Funcs := TMathFunctions.Create;
Funcs.Add(TMathBind.Create('+', TArithmeticProvider.Add, 2));
Funcs.Add(TMathBind.Create('-', TArithmeticProvider.Sub, 2));
Funcs.Add(TMathBind.Create('/', TArithmeticProvider.Divide, 2));
Funcs.Add(TMathBind.Create('*', TArithmeticProvider.Multi, 2));
Funcs.Add(TMathBind.Create('^', TArithmeticProvider.Power, 2));
Funcs.Add(TMathBind.Create('NEG', TArithmeticProvider.Negate, 1));
end;
destructor TArithmeticProvider.Destroy;
begin
Funcs.Free;
end;
function TArithmeticProvider.MathFunctions: TMathFunctions;
begin
Result := Funcs;
end;
Definicje funkcji matematycznych
class function TArithmeticProvider.Negate(Functor: TMathObject; Args: TMathArgs): Double;
begin
Result := -Args[0].ToFloat();
end;
class function TArithmeticProvider.Add(Functor: TMathObject; Args: TMathArgs): Double;
begin
Result := Args[0].ToFloat() + Args[1].ToFloat();
end;
class function TArithmeticProvider.Sub(Functor: TMathObject; Args: TMathArgs): Double;
begin
Result := Args[0].ToFloat() - Args[1].ToFloat();
end;
class function TArithmeticProvider.Divide(Functor: TMathObject; Args: TMathArgs): Double;
begin
if SameValue(Args[1].ToFloat(), 0.0) then
raise Exception.Create('Division by zero');
Result := Args[0].ToFloat() / Args[1].ToFloat();
end;
class function TArithmeticProvider.Multi(Functor: TMathObject; Args: TMathArgs): Double;
begin
Result := Args[0].ToFloat() * Args[1].ToFloat();
end;
class function TArithmeticProvider.Power(Functor: TMathObject; Args: TMathArgs): Double;
begin
if SameValue(Args[0].ToFloat(), 0.0) and SameValue(Args[1].ToFloat(), 0.0) then
raise Exception.Create('0 ^ 0');
Result := Math.Power(Args[0].ToFloat(), Args[1].ToFloat());
end;
Jak wspomniałem wcześniej, w tablicy Args znajdują się niezbędne argumenty do wyliczenia wartości funkcji. Ich ilość jest równa zadeklarowanemu parametrowi ArgsCount i parser ONP pobierze ze stosu tę właśnie ilość parametrów. Tablica Args jest listą obiektów typu TMathObject i dzięki niej możemy z łatwością rzutować typ danych na pożądany format. Obsługa nowego wzoru sprowadza się do stworzenia nowej funkcji zgodnie z sygnaturą TMathFunc.
Obliczanie wyrażenia ONP
Klasa TParser ma zaimplementowaną konwersję wyrażenia na notację ONP. Po wykonaniu metody InfixToPostfix, kolejka TQueue będzie zawierała uporządkowane elementy zgodnie z notacją ONP. Na tej podstawie obliczymy wartość wyrażenia.
Przebieg algorytmu
- Dla każdego symbolu notacji ONP:
- Jeśli symbol jest liczbą, wyjmij symbol z kolejki i odłóż na stos
- Jeśli symbol jest funkcją lub operatorem:
- Pobierz ze stosu odpowiednią ilość argumentów i wywołaj odpowiednią funkcję
- Odłóż wynik funkcji na stos
- Na szczycie stosu będzie wynik wyrażenia ONP.
Uzupełnienie klasy TParser o rejestrację funkcji
Klasie TParser brakuje implementacji metody Calc obliczającej wyrażenie ONP. Najpierw jednak dodamy możliwość rejestrowania utworzonych wcześniej funkcji matematycznych, które będą wykorzystywane podczas działania metody Calc. W tym celu dodamy słownik przechowujący nazwę funkcji oraz rekord typu TMathBind, który będzie zawierał informacje o funkcji oraz wskaźnik do niej.
Dodaj poniższy kod do deklaracji klasy TParser:
FFunctions: TDictionary<string, TMathBind>;
procedure RegisterProvider(Provider: IMathProvider);
Inicjalizacja słownika w konstruktorze:
FFunctions := TDictionary<string, TMathBind>.Create(20);
Oraz oczywiście zwolnienie pamięci w destruktorze:
FFunctions.Free;
Zdefiniujmy ciało funkcji RegisterProvider:
procedure TParser.RegisterProvider(Provider: IMathProvider);
var
Func: TMathBind;
begin
for Func in Provider.MathFunctions() do
FFunctions.Add(Func.Name, Func);
end;
Od tej pory możemy rozbudowywać parser o obsługę nowych funkcji.
Implementacja funkcji obliczajÄ…cej
procedure TParser.Calc;
var
MathBinder: TMathBind;
Res: Double;
MathArgs: TMathArgs;
begin
while FQueue.Count <> 0 do
begin
if not FQueue.Peek.IsFunction() then
FStack.Push(FQueue.Extract)
else
begin
if FFunctions.ContainsKey(FQueue.Peek.ToString()) then
begin
MathArgs := TMathArgs.Create;
MathBind := FFunctions.Items[FQueue.Peek.ToString()];
while (FStack.Count > 0) and (MathBind.ArgsCount > 0) do
begin
MathArgs.Add(FStack.Extract);
Dec(MathBind.ArgsCount);
end;
MathArgs.Reverse;
Res := MathBind.Func(FQueue.Peek, MathArgs);
FStack.Push(TMathObject.Create(Res));
MathArgs.Free;
end;
FQueue.Extract.Free;
end;
end;
FResult := FStack.Peek.ToFloat();
end;
Przykładowe użycie
Mając pełną implementację parsera ONP oraz definicje funkcji matematycznych możemy połączyć wszystko w jedną całość i przetestować efekt działania na prostej formule:
procedure btnTest_click(sender: TObject);
var
Parser: TParser;
Provider: IMathProvider;
begin
Parser := TLsCalc.Create;
Provider := TArithmeticProvider.Create;
try
Parser.RegisterProvider(Provider);
Parser.Calculate('-2+2*2');
ShowMessage(FloatToStr(Parser.GetResult));
finally
Parser.Free;
Provider.Free;
end;
end;
Na początku tworzymy obiekt klasy TParser oraz dostawcę z podstawowymi funkcjami matematycznymi. Provider rejestrujemy w instancji parsera. Testujemy wynik wprowadzając przykładowe wyrażenie matematyczne.
Wykorzystanie
JeÅ›li chcesz wykorzystać mój parser komercyjnie i/lub potrzebujesz pomocy aby go dostosować do swoich potrzeb – zapraszam do kontaktu.
Podsumowanie
W dwu-częściowym artykule przedstawiłem sposób na implementację algorytmu ONP. W sposób elastyczny można dodawać własne funkcje liczące skomplikowane wyrażenia.
W przypadku znalezienia błędów lub wątpliwości proszę o kontakt poprzez formularz lub komentarz.
Strona Internetowa
Potrzebujesz ładnej strony internetowej? Zobacz demo na: tej stronie
Komentarze